Analysis of for loop

Question

Consider this fragment of code

int sum = 0;
for( int i = 1; i <= n*n; i = i*2 ){
   sum++ ;
}

How to do a quick proper analysis for it to get order of growth of the worst case running time?

How does changing the increment statement to i = i * 3 instead of i = i * 2 changes the worst case running time?

And is our analysis affected by changing comparison operator to < instead of <= ?

i don't understand your question... Are you asking what the loop is doing and how it would behave if you replace i*2 by i*3 and < by <= ? by the way... we're not here to do your homework... — Kraal, Sep 21 '14 at 18:12
possible duplicate of [Plain English explanation of Big O](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) — Whymarrh, Sep 21 '14 at 18:16
i want to get the order of growth of the worst case running time — iartist93, Sep 21 '14 at 18:18

score 4 · Answer 1 · answered Sep 21 '14 at 18:11

4

Actualy this loop is infinte loop.

i=0
i=i*2  //0*2=0

So this loop will never end. Make i=1 to get the count of powers of 2 till n^2 not sum.

answered Sep 21 '14 at 18:11

Pratyush Khare

689
5
16

1

this should be a comment, not an answer. – Haris Sep 21 '14 at 18:12
5

Hard for someone to comment with less than 50 rep – Damian Sep 21 '14 at 18:12
I cant comment. I do not have enough priviledge. Thanks @Damian for pointing out. – Pratyush Khare Sep 21 '14 at 18:13
Sorry i've changed it to to begin from i=1 no 0, it's my fault sorry! – iartist93 Sep 21 '14 at 18:17

axiom · Accepted Answer · 2014-09-22T05:06:57.843

int sum = 0;
for( int i = 0; i <= n*n; i = i*2 ){
   sum++ ;
}

As it stands, this is an infinite loop which will never stop, since i is never changing. As complexity is defined for only Algorithms, which by definition should terminate in finite amount of time, it is undefined for this snippet.

However, if you change the code to the following :

int sum = 0;
for( int i = 1; i <= n*n; i = i*2 ){
   sum++ ;
}

We can analyze the complexity as follows:

Let the loop run k - 1 times, and terminate at kth updation of i. Since it's better to be redundant than to be unclear, here is what is happening:

Init(1) -> test(1) -> Loop(1) [i = 1]->
Update(2) -> test(2) -> Loop(2) [i = 2]->
...
Update(k - 1) -> test(k - 1) -> Loop(k - 1) [i = 2 ^ (k - 2)] ->
Update(k) -> test(k)->STOP [Test fails as i becomes 2 ^ (k - 1)]

Where Update(k) means kth update (i = i * 2).

Since, the increments in i are such that in the pth loop (or equivalently, after pth updation), the value of i will be 2 ^ (p - 1), we can say that at termination:

2 ^ (k - 1) > (n * n)

In verbose, we have terminated at the kth updation. Whatever the value of i was, it would've been greater than (n * n) or we would have gone for the kth loop. Taking log base 2 on both sides:

 k ~ 2 * log(n)

Which implies that k is O(log(n)).

Equivalently, the number of times the loop runs is O(log(n)).

You can easily extend this idea to any limit (say n*n*n) and any increments (i*3, i*4 etc.)

The Big O complexity will be unaffected by using < instead of <=

Thanks @axiom :) got it .. but i wonder if there method for analysing — iartist93, Sep 21 '14 at 18:42

score -1 · Answer 3 · answered Sep 21 '14 at 18:15

for any loop, to analys it. u have to see 2 things. the condition that will make it exit, and the iteration applied to the variable used in the condition..

for your code. u can notice that the loop stops when i goes from 0 to n*n (n^2). and the variable i is increasing like i = i*2. as i is increasing i in this manner, the loop would run for log (n^2) times. this you can see by taking an example value of n^2, like 128, and then iterate it manually one by one.

Analysis of for loop

3 Answers3