Apr 14, 2013 at 6:15am UTC
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.
Apr 14, 2013 at 6:39am UTC
> 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')
Apr 14, 2013 at 6:45am UTC
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 Apr 14, 2013 at 7:04am UTC
Apr 14, 2013 at 12:51pm UTC
I just gave an example. didn't look in detail.. :-)
So, it would be kn, where k would be a constant less than n.
Apr 14, 2013 at 1:09pm UTC
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.
Apr 14, 2013 at 7:43pm UTC
In the inner loop you've got j increasing and n decreasing.
It ends with j>n, so it would be equivalent to
1 2 3
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.
Last edited on Apr 14, 2013 at 7:44pm UTC