### The cost of an algorithm

how i can calculate The cost of this algorithm?

 123456789 for(int i=1 ; i<=n ; i++) { sumi += 1 ; for(int j = 1 ; j <=n ; j++) { sumj +=1 ; n = n - 1 ; } }
cost of algorithm is generally total steps or times the code executes itself. So, it has n * n steps and the cost is n^2.

in calculation of cost, constant factors are not taken in consideration. So, whatever is going inside the loops is ignored.

> it has n * n steps and the cost is n^2.
nope, see line 7.
It is O(n)

(the number of iterations is stored in sumj')
n : ----> 1 2 3 4 5 6 7 8 9 10

sumi :->1 2 1 2 2 2 2 2 2 2

sumj :->1 2 2 3 4 5 6 6 7 8
Last edited on
¿?
I just gave an example. didn't look in detail.. :-)

So, it would be kn, where k would be a constant less than n.
n=2 cannot lead to sumi=2, sumj=2, because after first step in inner loop n is already reduced to 1, preventing second step on both inner and outer loops.

The number of inner loop steps that do get executed is continuously a bit less than n, but that seems like a constant so O(n) it is.
In the inner loop you've got j increasing and n decreasing.
It ends with j>n, so it would be equivalent to
 123 for(int j=0; j

Now the outer loop ends with i>n, but n will be halved every time. By definition it would execute lg(n) times.

So you have \sum_{k=0}^{k=lg(n)} \frac{n}{2^k}'
which is a geometric series, that tend to n.
Last edited on
Topic archived. No new replies allowed.