Quiz 1 on Time and Space Complexity

#1

Hi sir,

I’m a little bit confused about the Quiz 1. Why the time complexity is O(N)?

I think when i = N then the innermost loop will take N times to execute. The outermost could take logN times because it reduces a helf after each step.

Thanks for your help.

#2

@halihoof
lets check it line by line for every i.
For a input integer n, the innermost for loop is executed following times.
n + n/2 + n/4 + … 1
So time complexity T(n) can be written as
T(n) = O(n + n/2 + n/4 + … 1) = O(n).

#3

@sdevwrat Thank you a lot. I got it

1 Like