Master's Method
Solving Recurrences for Divide and Conquer Algorithms

The Master's Method:

• T(n) is O(n^{log_b a}) , if a > b^k
• T(n) is O(n^k log n) , if a = b^k
• T(n) is O(n^k) , if a < b^k

Proof:

T(n) = a T(n/b) + O(nk)      (1)
       = a [aT(n/b2) + O((n/b)k)] + O(nk)     (2)
       = a [a[aT(n/b3) + O((n/b*b)k)] + O((n/b)k) ] + O(nk)    (3)
       = ...
       = aiT(n/bi) +S j=0i-1 aj O((n/bj)k)  (i)
       = aiT(n/bi) + O(nk) S j=0i-1 O((a/bk)j) 

Let i = logbn (n = bi) and T(1) = O(1), 
T(n) = alogb n T(1) + O(nk) S j=0logb n -1O((a/bk)j)  
     = nlogb a + O(nk)S j=0logb n -1O((a/bk)j)  



 If a = bk, then logba = k (defn of log), and
T(n) = nlogb a + O(nk) S j=0logb n -1 O((a/bk)j)
     = nlogb a + O(nk) S j=0logb n -1 O(1j)  
     = nlogb a + O(nk) O(logb n -1)
     = nk + O(nklogb n)  = O(nklogb n)     

 If a < bk, then logba < k 
0 < a/bk < 1, so the largest term of the sum is when j = 0 because (a/bk)0 = 1.

T(n) = nlogb a + O(nk) S j=0logb n -1O((a/bk)j)
     = O(nlogb a) + O(nk) + ... smaller terms ...
     = O(nk)  because logba < k
  
If a > bk, then logba > k,
a/bk > 0, so the largest term of the sum is when j = logbn  - 1.

T(n) = nlogb a + O(nk)S j=0logb n -1O((a/bk)j)
     = O(nlogb a) + O(nk(a/bk)logb n) + ... smaller terms ...
     = O(nlogb a) + O(nknlogb a/bklogb n)
     = O(nlogb a) + O(nknlogb a/nklogb b)
     = O(nlogb a) + O(nlogb a)
     = O(nlogb a)