The Curtain Rises on Time Complexity

Let's talk about the speed of our code. We take our input number n and divide it by 2 until we reach the base case. How many times can you halve a number until you reach the smallest whole number? Well, that's log base 2 of n.

Imagine this as a countdown timer that speeds up every second. It starts slow but gets quicker until it reaches zero. That's logarithmic time for you!

1while n > 0:
2    # perform some operations
3    n = n // 2

Unpacking the Space Complexity: A Box of log n Bits

Hold your applause! We're not done yet. What about the space our code occupies?

Well, every time we halve n, we either add a 0 or a 1 to our binary string. Just like our time complexity, we're doing this log base 2 of n times.

1binary_array = []
2while n > 0:
3    binary_array.append(n % 2)
4    n = n // 2

The Grand Reveal: O(logn)

Both the time and space complexity of this enchanting algorithm are O(logn).