March 23, 2025.
Recently I've learned about Master Theorem, which describes the runtime for some recursive algorithms.
This page hopes to explain this theorem intuitively.
You can probably guess that the time complexity of this program is $O(lg(n))$.
void f(int n){
if (n==0) return;
f(n/2);
}
If you think hard enough, this is $O(2^{lg(n)}) = O(n)$,
void f(int n){
if (n==0) return;
f(n/2);f(n/2);
}
and this is $O(3^{lg(n)}) = O(n^{lg(3)})$.
void f(int n){
if (n==0) return;
f(n/2);f(n/2);f(n/2);
}
In general, this is $O(a^{log_b(n)}) = O(n^{log_b(a)})$.
void f(int n){
if (n==0) return;
for (int i=0;i<a;i++) f(n/b);
}
By the way, if you are wondering why certain algorithms have time complexity $O(n^{lg(3)})$, this is pretty much what they do.
More generally, suppose we have an algorithm $P(n)$ where we need to compute $a$ subproblems with size $\frac{n}{b}$.
Define the time complexities:
Then the time complexity of $P(n)$ has the recurrence $T(n)=a\cdot T(\frac{n}{b})+F(n)$.
Given this recurrence, Master's Theorem can help find an explicit description of $T(n)$.
Intuitively, $T(n)$ can be found by comparing $F(n)$ against the number of recursive calls in $T(n)$.
Based on the results of the introductory example, the number of recursive calls is $O(n^{log_b(a)})$.
In fact, the key condition of Master's Theorem asks which of these is faster: $F(n)$ or $O(n^{log_b(a)})$.
If $F(n)$ is faster than $O(n^{log_b(a)})$, then $T(n) = O(n^{log_b(a)})$.
If $F(n)$ is slower than $O(n^{log_b(a)})$, then $T(n)$ is at least $F(n)$.
Why at least $F(n)$? Well because "many small $F$'s can dominate one large $F$".
We can rewrite the recurrence as: $$T(n) = F(n) + a\cdot T(\frac{n}{b})$$ $$= F(n) + a\cdot F(\frac{n}{b}) + a^2\cdot T(\frac{n}{b^2})$$ $$\dots$$ $$= F(n) + a\cdot F(\frac{n}{b}) + a^2\cdot F(\frac{n}{b^2}) + a^3\cdot F(\frac{n}{b^3}) + \dots$$
If we add the additional condition that $F(n)$ dominates $a\cdot F(\frac{n}{b})$, then we can be absolutely certain that $T(n)=F(n)$.
Formally, this condition is $F(n) > k F(n) \geq a\cdot F(\frac{n}{b})$, for some constant $k$ (this is called the "regularity" condition).
Sometimes, the regularity condition fails. In the case where $F(n) = a\cdot F(\frac{n}{b})$, notice that there are $O(log_b(n))$ terms in the summation of $F$'s for $T(n)$. Hence, $T(n) = F(n)\cdot O(log_b(n)) = F(n)\cdot O(lg(n))$.
One (unmotivated) example is $F(n)=n^{log_b(a)}\cdot (lg(n))^k$, for some constant $k$: $$a\cdot F(\frac{n}{b})$$ $$=a\cdot {(\frac{n}{b})}^{log_b(a)}\cdot (lg(\frac{n}{b}))^k$$ $$=a\cdot {(\frac{n}{b})}^{log_b(a)}\cdot O(log_b(\frac{n}{b})^k)$$ $$=a\cdot a^{log_b(\frac{n}{b})}\cdot O((log_b(n)-1)^k)$$ $$=a^{log_b(n)}\cdot O(log_b(n)^k)$$ $$=n^{log_b(a)}\cdot O(lg(n)^k)$$ $$=F(n)$$ Here, $T(n)=F(n)\cdot lg(n) = n^{log_b(a)}\cdot (lg(n))^{k+1}$
Now let's see Master Theorem with an example!
In merge sort, the list is halved into two sublists, and each is sorted via merge sort.
After sorting both sublists, an $O(n)$ algorithm merges the sublists together.
Hence, merge sort can be described by $a=2$, $b=2$, $F(n)=O(n)$. It has recurrence $T(n)=2\cdot T(\frac{n}{2})+O(n)$.
Notice that $O(n^{log_b(a)})=O(n^{log_2(2)})=O(n)=F(n)$. Hence by Master Theorem, merge sort has time complexity $O(n\cdot lg(n))$.
back