What's the time complexity when j increases by j += log(j+5)?

Question

Consider the following code:

int j = 1;

while (j < n) {

    j += log( j + 5 )

}

How to calculate the time complexity?

Answer 1

One way to think about this question is to break the range that j starts from and ends at, into two parts:

j starts from 1, reaches n.

Let us break this into two separate journeys:

• Part 1: j goes from 1 to sqrt(n)
• Part 2: j goes from sqrt(n) to n.

Let us analyze these two separately.

• Part 1 - This can not take more than O(sqrt(n)) time
• Part 2 - This can not take more than O(n / log (sqrt(n))) time.

We observe that O(n/log (sqrt(n))) = O( 2 n / log n) = O(n / log n) time.

Therefore, total time = O(sqrt(n)) + O(n/log n), that is, O(n/log n)