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?

- All categories
- Asymptotic Analysis (22)
- Divide & Conquer (9)
- Greedy Algorithms (2)
- Dynamic Programming (7)
- Backtracking/DFS/BFS (2)
- Branch & Bound (2)
- Graph Theory (15)
- NP-Completeness (4)

+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)

...