educative.io

Educative

Why Complexity is O(n)?

A reader asked us the following question:

I think challenge 7 is wrong please validate. Answer I think is nlogn

The complexity of this algorithm cannot be O(nlog(n)) because the counter of the inner loop is doubled in each iteration. The inner while loop will run log2(N) times for all the iterations of the outer loop. On the other hand, the outer loop will run n times. Therefore, the overall complexity will be O(n).

To make things simpler, consider n = 10000. Even for such a large value of n inner loop will run 14 times in total because the inner loop counter is multiplied by 2 in each iteration. The outer loop will run 10000 times. The overall complexity will be:

N+log2(N) = O(N)

2 Likes

Clearly the analysis in the course is wrong. It says the inner loop enters for each iteration of outer loop but it actually does only once. This didn’t seem to be a “Pro” level question. I suspect the while statement was meant to be an if statement? That can definitely complicate things.

Hi Stayam,

Thanks for reaching out! We have fixed the issue in this lesson. If you have any other questions/comments/suggestions, let us know!