Asymptotic analysis, recursion trees and the master theorem

Running times are compared by their growth, ignoring constant factors and small inputs. We write \( f(n) = O(g(n)) \) if there are constants \( c > 0 \) and \( n_0 \) with \( f(n) \le c\,g(n) \) for all \( n \ge n_0 \); \( f = \Omega(g) \) for the matching lower bound, and \( f = \Theta(g) \) when both hold. For example \( 3n^2 + 10n = O(n^2) \), with witnesses \( c = 4 \) and \( n_0 = 10 \). A convenient test: if \( f(n)/g(n) \) tends to a finite positive limit then \( f = \Theta(g) \), and if it tends to 0 then \( f = O(g) \) but not \( \Theta(g) \). The example confirms that \( n\log n \) grows strictly more slowly than \( n^2 \).

The running time of loops is a sum. A pair of nested loops, the inner one running from \( i + 1 \) to \( n \), performs \( \sum_{i=1}^{n}(n - i) = n(n-1)/2 = \Theta(n^2) \) steps. A loop that halves its variable each time runs about \( \log_2 n \) times, which is why binary search is \( \Theta(\log n) \).

Divide and conquer gives recurrences instead. Merge sort splits the input in half, sorts each half recursively and merges in linear time: \( T(n) = 2T(n/2) + n \). A recursion tree solves it by drawing the calls: the root does \( n \) work, its two children do \( n/2 \) each, the four grandchildren \( n/4 \) each, so every level does \( n \) work in total, and there are \( \log_2 n + 1 \) levels. Hence \( T(n) = \Theta(n\log n) \); exactly, with \( T(1) = 1 \), \( T(2^k) = (k+1)2^k \).

The master theorem packages the recursion tree for \( T(n) = a\,T(n/b) + f(n) \) with \( a \ge 1 \), \( b > 1 \). The number of leaves is \( a^{\log_b n} = n^{\log_b a} \), and the answer depends on how \( f(n) \) compares with \( n^{\log_b a} \). If \( f(n) = O(n^{\log_b a - \varepsilon}) \) for some \( \varepsilon > 0 \), the leaves dominate and \( T = \Theta(n^{\log_b a}) \). If \( f(n) = \Theta(n^{\log_b a}) \), every level contributes equally and \( T = \Theta(n^{\log_b a}\log n) \). If \( f(n) = \Omega(n^{\log_b a + \varepsilon}) \) and the regularity condition \( a\,f(n/b) \le c\,f(n) \) holds for some constant \( c < 1 \) and all large \( n \), the root dominates and \( T = \Theta(f(n)) \). The cases do not cover everything: \( f(n) = n^{\log_b a}\log n \), for instance, falls between the second and third, and needs the recursion tree directly. Karatsuba multiplication, \( T(n) = 3T(n/2) + n \), is in the first case: \( \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585}) \).

Picture it: the recursion tree as a triangle of work. If the levels get heavier towards the bottom, the leaves win; if they are all equal, the total is one level times the height; if they get lighter, the root wins.

Think it: constant factors matter in practice and asymptotics matter at scale. An algorithm that is \( \Theta(n^2) \) with a small constant can beat a \( \Theta(n\log n) \) one on short inputs, which is why library sorts switch to insertion sort on small pieces. But the growth rate decides what is feasible for large \( n \), and no constant factor rescues an exponential algorithm.