Proof of the Master Theorem

Proof of the Master Theorem Theorem 1. [Master Theorem] Let a ≥ 1 and b > 1 be constants, and let f (n) be an asymptotically positive function. Let T (n) be defined, for integers n > 0, as T (n) = aT (n/b) + f (n). Then: 1. If f (n) = O(n(logb a)− ) for some constant  > 0, then T (n) = Θ(nlogb a ). 2. If f (n) = Θ(nlogb a ), then T (n) = Θ(nlogb a lg n). 3. If f (n) = Ω(n(logb a)+ ) for some constant  > 0 and af (n/b) ≤ cf (n) for some constant c < 1 and sufficiently large n, then T (n) = Θ(f (n)). For now we will assume that n is a power of b, but this is not, in general, required. Our proof will make use of two lemmas. Lemma 1. Let T (n) be defined as follows for integers n > 0: ( Θ(1) n=1 T (n) = . aT (n/b) + f (n) n = bi , (i integer, i > 0) Then (logb n)−1 logb a T (n) = Θ(n )+ X aj f (n/bj ). j=0 Lemma 2. Let (logb n)−1 g(n) = X aj f (n/bj ). j=0 Then g(n) has the following asymptotic bounds: 1. If f (n) = O(n(logb a)− ) for some constant  > 0, then g(n) = O(nlogb a ). 2. If f (n) = Θ(nlogb a ), then g(n) = Θ(nlogb a lg n). 3. If af (n/b) ≤ cf (n) for some constant c < 1 and sufficiently large n, then g(n) = Θ(f (n)). Proof. [Master Theorem] By Lemma 1, we have: Case 1: f (n) = O(n(logb a)− ) for some constant  > 0. Then by Lemma 2, we have g(n) = . So we conclude that T (n) = . Case 2: f (n) = Θ(nlogb a ). Then by Lemma 2, we have g(n) = . So we conclude that T (n) = . Case 3: f (n) = Ω(n(logb a)+ ) for some constant  > 0, and af (n/b) ≤ cf (n) for some constant c < 1 and sufficiently large n. Then by Lemma 2, we have g(n) = . So we conclude that T (n) = . Proof. [Lemma 1] Sketch the recursion tree for the recurrence T (n): How many nodes are there at level j? What is the cost of each node at level j? What is the depth of the tree? What is the total cost of all internal nodes (i.e., excluding leaves)? How many leaves are there? What is the cost of each leaf? What is the total cost of the entire tree (internal nodes plus leaves)? Proof. [Lemma 2] Case 1: f (n) = O(n(logb a)− ) for some constant  > 0. What is the asymptotic class of f (n/bj )? Plug this result into g(n) and simplify: Case 2: f (n) = Θ(nlogb a ). What is the asymptotic class of f (n/bj )? Plug this result into g(n) and simplify: Case 3: af (n/b) ≤ cf (n) for some constant c < 1 and sufficiently large n. Why can we say immediately that g(n) = Ω(f (n))? Next we need to show that g(n) = O(f (n)). Rewrite the regularity condition af (n/b) ≤ cf (n) by dividing both sides by a: Iterate j times: Multiply both sides by aj : Plug this result into g(n) and simplify: Combining these two results, we get that g(n) = Θ(f (n)).