The cost of an algorithm

[smemamian]

how i can calculate The cost of this algorithm?

for(int i=1 ; i<=n ; i++)
    {
        sumi += 1 ;
        for(int j = 1 ; j <=n ; j++)
        {
            sumj +=1 ;
            n = n - 1 ;
        }
    }

[writetonsharma]

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.

read about time complexity to understand.

[ne555]

> 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')

[smemamian]

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

[ne555]

¿?

[writetonsharma]

I just gave an example. didn't look in detail.. :-)

So, it would be kn, where k would be a constant less than n.

[keskiverto]

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.

[ne555]

In the inner loop you've got j increasing and n decreasing.
It ends with j>n, so it would be equivalent to

for(int j=0; j<n/2; ++j)
   ;
n/=2;

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.