- Published on
The simple math behind log(n) time complexity
- Authors
- Name
- Faddal Ibrahim
- @FaddalIbrahim
Introduction
I know you are quite the algo wonderkid, but here is a question that might knock you off your high horse - what does a time complexity of really mean?
Well, you would reference binary search and say, halving the problem size at each step results in . But it's still vague. What does even mean? How did steal the spotlight? What's the root derivation? Where does it come from?
Unlike and , which are quite intuitive, is derived quite differently.
In 3 steps, I will build upon micro analogies already familiar to you to lead to that big eureka moment. Calmly stay with me and let's find out!
Inverse operations in mathematics
Let me bore you a little with primary school math - Plus (+) is the opposite of minus (-) and division (/) is the opposite of multiplication (*).
As such, can be re-written as . In natural language, we say 2 added to 8 is 10
and 10 subtracted from 8 is -2
respectively. There are a few other ways to re-arrange the same equation but expressing them in natural language will be different. The same can be applied to 2 * 10 = 20
and 2 = 20/10
.
This simple yet powerful logic is the reason we are able to easily solve algebraic equations. We could go a bit further to reference trigonometric and square root inversions, but we have enough base to proceed.
Indices and Logarithms
Indices are intuitive. is mathematically read as 3 raised to the power of 4 is 81
. In natural language, multiplying 3 by itself 4 times gives 81
.
Now let's introduce Logarithms, which are the inverse of indices.
Just as we can re-write as , we can also re-write as .
The image below summarizes the inverse relationship.
is mathematically read as log base 3 of 81 is 4
. Expressing in natural language is where it makes a lot of sense.
:
- Natual Language :
3 raised to the power/exponent of 4 is what?
:
- Natural Language:
To get 81, what power/exponent do we raise 3 to?
- Or more clearly:
To get 81, how many times do we need to multiply 3 by itself?
Notice how the Logarithms rephrase the question by starting with the ANSWER! (Refer back to the diagram for a visual representation)
The math
In binary search, we repeatedly halve the problem size until we reduce it to a size of 1.
The time complexity is basically how many times do we need to halve the problem size to reach that final size of 1. Sounds familiar? Absolutely yes - because that is exactly what logarithms represent!
In the illustration below, the input size is 8, which gets halved 3 times to get the final input size of 1
Hence, given an initial problem size of n
, mathematically, all we are saying is
if we use x
to represent that unknown number of times needed to halve the problem size to 1, we now have
which, upon further simplification, becomes
From here, we can proceed in 2 ways
1. Directly rewrite the exponential equation as a logarithm
2. Mathematically solve for x using rules of logarithms
Take the logarithm (base 2) of both sides:
Apply the logarithm Power Rule
Apply the Identity Rule
Finally:
Mic Drop!
References
Logarithm Fundamentals - 3Blue1Brown
Khan Academy - Logarithms