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

0 votes

It's about the problem 4 in project 1.

Let's extract the code as:

int j = 1;

while (j < n) {

    j += log( j + 5 )

}

So how to calculate the time complexity?

asked Sep 10 in Asymptotic Analysis by Yan Zhang (132 points)

1 Answer

+1 vote
 
Best answer

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)

answered Sep 13 by Amrinder Arora (206 points)
selected Oct 28 by Amrinder Arora
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...