Algorithm complexity with iterations. Is it logarithmic or exponential?

Question

If I have the following algorithm

for (i = 1; i <= 4 * n; i = i * 4) {
   for (k = 1; k < 1000; k = 2 * k) {
       print(k);
   }
   print(i);
}

how can I calculate its complexity? I only understand that for one iteration of for(i=1; i≤4n; i=i*4), the line with print(i) is O(1), and for one iteration of for(k=1; k<1000; k=2*k), the line with print(k) is O(1).

I'm not sure how to proceed.

Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Prune, Mar 22 '19 at 21:44
If you search on the phrase "determine computational complexity" or any [reference](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) on SO, you’ll find resources that can explain it much better than we can in an answer here. — Prune, Mar 22 '19 at 21:56

score 3 · Accepted Answer · answered Mar 22 '19 at 17:48

Here's the inner loop:

for(k=1; k<1000; k=2*k) {
    print(k);
}

That loop is constant time, because there are no free variables. It's always going to call print exactly 9 times, for k ∈ {1,2,4,8,16,32,64,128,256,512}.

The outer loop is O(log n), because it will execute ⌊log₄ 4n⌋ times.

Overall, the program fragment you posted (if we add the final closing brace you omitted) is O(log n).

Algorithm complexity with iterations. Is it logarithmic or exponential?

1 Answers1