0

I have to check the time complexity of the following code:

while n > 0 :
n //= 2

Of course the n will be divided to the moment when it will be so small the computer will recognize it as 0. Something tells me that the time complexity of it is logn but I'm not sure how to prove it. Any tips on that?

Sarghhh
  • 3
  • 2
  • Does this answer your question? [What does O(log n) mean exactly?](https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly) – kaya3 Mar 09 '22 at 11:17

1 Answers1

1

I think reasoning in the opposite way could be more intuitive:

You start from a certain n₀, that is the lowest positive number recognized, and at each step (i.e., for each unit of time t) you multiply it by 2 until, at a certain time t*, you reach a certain n*, that in your question corresponds to the original value of n.

The value of n* will be:

n₀*2*2*2*2*2*...*2*2*2*2*2
   |___number of steps___|

i.e., n* = n₀*2^(t*). In general, we have that n = n₀*2^t and, reasoning asymptotically, since n₀ is a constant factor, we have that n∈O(2^t).

Thus, doing a re-inversion, we have that the time complexity is logarithmic w.r.t. n (indeed, it is O(log₂(n))).

logi-kal
  • 7,107
  • 6
  • 31
  • 43
  • Is it typical for time complexities to just say `log n` instead of `log₂ n`? What base do you assume? – Freddy Mcloughlan Mar 09 '22 at 11:31
  • @FreddyMcloughlan The base of the logarithm is 2, as the base of the exponential is also 2. Anyway, usually the base is not so important. – logi-kal Mar 09 '22 at 11:48