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 (116 points)

1 Answer

+1 vote
One way to think about this question is as follows:

j starts from 1, reaches n.

j increments by log(j+5), which can be as small as 1, or as large as log (n), about.

So, this loop runs no more than n times, and no less than n/log n times.
answered Sep 13 by Amrinder Arora (38 points)
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...