Time complexity of this for loop: for (i = 2; i &l

问题:

We're learning about time complexity right now and I'm having a ton of trouble with this one example.

for (i = 2; i < n; i = i * i)
{
     ... do something ...
}

The prof said that it was O(sqrt(N)), but I'm not sure that I'm convinced. After all, if N=16, it only runs 2 times, not 4 right?

My approach to solution: 2^(2k) = N, where k is the number of times the loop runs. Removing the constant factors, k runs log(N) times. Where am I going wrong here? Thanks for any advice on the matter.

回答1:

You are correct that your instructor is wrong (at least, their bound isn't tight), and I like the analysis you've done, but I think that you've come to the wrong conclusion in the final step.

It's great that you looked at all the intermediary values along the way. You're correct that the sequence of values that j takes is 2, 4, 16, 256, etc. If we rewrite things as powers of two, notice that the sequence takes on the values

2¹, 2², 2⁴, 2⁸, ...

More generally, after k iterations of the loop, the value of j is 2^2k (as opposed to 2^2k, as you initially wrote). This means that to determine the number of loop iterations, you want to determine when

2^2k = n.

Here, you have to take two logarithms to solve this:

2^2k = n

2^k = lg n

k = lg lg n

So the number of iterations of the loop is O(log log n), lower than both the O(√n) that your teacher gave you and the O(log n) that you came up with.

For what it's worth, you often see O(log log n) behavior when you repeatedly take square roots of a number (you can take the square root of a number O(log log n) times before it drops to a constant), and so it's not super surprising that if you run this in reverse and keep squaring a value that you'd see O(log log n) show up.

回答2:

When you use the big O notation, you are talking about the behavior when N goes to infinity. N = 16 is not large enough.

That being said, I don't think your professor is right. For a loop

for (int i = 0; i*i < N; ++i) { ...}

will have a time complexcity of O(sqrt(N)).

For your loop, you are right, it should be O(log(log(N))) since the loop runs when i = 2, 4, 16, ..., 2^k, ... which 2^k >=N.