How the time complexity of the following code is O(n)?

Question

I was solving a time-complexity question on Interview Bit, which is given below in the image.

The correct answer to this question is O(N). But according to me, the answer should be O(NlogN). Since the complexity for the first "for loop" should be O(logN) because the variable i is divided by 2 in each iteration and I have studied that whenever the loop variables are either multiplied or divided by 2, then the time complexity is O(logN). Now, for the second "for loop", the complexity should be O(N), therefore, the final complexity should be O(N*logN).

Can anyone please explain where I am wrong?

Note that O(NlogN) is not actually wrong since O() is an upper bound. It's just less informative than O(N). — Gassa
Where you went wrong is that while the outer loop is entered O(log N) times, providing the idea that maybe the whole algorithm does take O(? * log N), the inner loop does not execute an average of cN times for some constant c, for each execution of the outer loop. As IVlad's answer states, you need to do the math leading to the geometric series. — moreON

IVlad IVlad · Accepted Answer · 2017-02-14T10:20:38

Do the actual math:

T(N) = N + N/2 + N/4 + ... + 1 (log_2 N terms in the sum)

This is a geometric series with ratio 1/2, so the sum is equal to:

T(N) = N*[1 - (1/2)^(log_2 N)] / (1 - 1/2) =
     = [N - N/(2^log_2 N)] / 0.5 =
     2^log_2 N = N
     = (N - 1) / 0.5

So T(N) is O(N).

How the time complexity of the following code is O(n)?

1 Answers