What will be the time complexity of this code fragment?

Question

Given this question where increment over the iterator i happens by incrementing its value by its own log value. What will be the big O time complexity for this fragment?

i = 10
while(i<n) {
    i=i+log(i);
}

Answer 1

Interesting question! Here's an initial step toward working out the runtime.

Let's imagine that we have reached a point in the loop where the value of i has reached 2^k for some natural number k. Then for i to increase to 2^k+1, we'll need approximately 2^k / k iterations to elapse. Why? That's because

• The amount i needs to increase is 2^k+1 - 2^k = 2^k(2 - 1) = 2^k, and
• At each step, increasing i by log i will increase i by roughly log 2^k = k.

We can therefore break the algorithm apart into "stages." In the first stage, we grow from size 2³ to size 2⁴, requiring (roughly) 2³/3 steps. In the second stage, we grow from size 2⁴ to size 2⁵, requiring (roughly) 2⁴ / 4 steps. After repeating this process many times, we eventually grow from size n/2 = 2^{log n - 1} to size n = 2^{log n}, requiring (roughly) 2^{log n} / log n steps. The total amount of work done is therefore given by

2³ / 3 + 2⁴/4 + 2⁵ / 5 + ... + 2^{log n} / log n.

The goal now is to find some bounds on this expression. We can see that the sum is at least equal to its last term, which is 2^{log n} / log n = n / log n, so the work done is Ω(n / log n). We can also see that the work done is less than

2³ + 2⁴ + 2⁵ + ... + 2^{log n}

≤ 2^{log n + 1} (sum of a geometric series)

= 2n,

so the work done is O(n). That sandwiches the runtime between Ω(n / log n) and O(n).

It turns out that Θ(n / log n) is indeed a tight bound here, which can be proved by doing a more nuanced analysis of the summation.