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!
PYTHON
1while n > 0:
2 # perform some operations
3 n = n // 2Unpacking 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.
PYTHON
1binary_array = []
2while n > 0:
3 binary_array.append(n % 2)
4 n = n // 2The Grand Reveal: O(logn)
Both the time and space complexity of this enchanting algorithm are O(logn).
