CODEWITHSUNDEEP
algorithmtime-complexitybig-oasymptotic-complexity
SherlockHolmesKePapa
SherlockHolmesKePapa

Reputation: 643

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

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

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?

Upvotes: 0

Views: 814

Answers (2)

Aman Singh
Aman Singh

Reputation: 1

the answer to this question is O(N^2)

Upvotes: -1

IVlad
IVlad

Reputation: 43517

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

Upvotes: 4

Related Questions