Time Complexity

[khushib]

Hello
Can you please let me know how to find the growth function and order of following loop?

for(int i=0; i<n; i*=2){
/* O(1) steps
}


Thanks!

[Stang02GT]

1st we don't do your homework for you.


2nd I don't even know what that is lol

[RedSon]

Hi,

Please try to do your homework on your own, look through your textbook and use online resources.

Here is a good article to get you started http://en.wikipedia.org/wiki/Big_O_notation

[RedSon]

Hi,

Please try to do your homework on your own, look through your textbook and use online resources.

Here is a good article to get you started http://en.wikipedia.org/wiki/Big_O_notation

Actually on second thought this one probably provides more useful information as an introductory:

http://en.wikipedia.org/wiki/Analysis_of_algorithms

[tlhintoq]

While I agree with others here that its your homework and asking someone else for the answer is not the same as "research", I am big on trying to get people to think for themselves. Going to a calculator to solve 2+2 is why store clerks can't give change now days.

So I might suggest... Look at the formula, walk through it and think for yourself. This is not a process of quantum string theory; its a darn simple loop.

for(int i=0; i<n; i*=2){
/* O(1) steps
}

First it won't compile because you have started comments in the second line without ending the comments, so the closing brace is still a comment.

Second... What is the initialization of the loop saying?
'Start with i equal to zero, continue as long as i is less than n, for each iteration double the value of i'

Third.. Walk through the loop in your head. See it. Seeing what the code is doing to to values/variable is vital to coding. If you don't see it you can't write it or fix it. What will happen when i is 2, 3, 4?

[Stang02GT]

khushib,

Seeing as how Redson and tlhintoq have provided you with enough information to help you. If you attempt the problem and get stuck. Please post back so we can see that you are making an effort to do it on your own and we can help you a little more.

We just don't want you to post your homework and expect us to do it for you. If you attempt it and post where you are stuck we can provide guidence and help to you.

[JosAH]

For any n > 0 that loop never terminates so any big-Oh question won't make sense.

kind regards,

Jos