# Recurrences Essay

1814 WordsMar 14, 20148 Pages
Recurrences (CLRS 4.1-4.2) • Last time we discussed divide-and-conquer algorithms Divide and Conquer To Solve P: 1. Divide P into smaller problems P1 , P2 , P3 .....Pk . 2. Conquer by solving the (smaller) subproblems recursively. 3. Combine solutions to P1 , P2 , ...Pk into solution for P. • Analysis of divide-and-conquer algorithms and in general of recursive algorithms leads to recurrences. • Merge-sort lead to the recurrence T (n) = 2T (n/2) + n – or rather, T (n) = Θ(1) T( n ) + T( 2 n 2 If n = 1 ) + Θ(n) If n > 1 – but we will often cheat and just solve the simple formula (equivalent to assuming that n = 2k for some constant k, and leaving out base case and constant in Θ). Methods for solving recurrences 1. Substitution method 2. Iteration method • Recursion-tree method • (Master method) 1 Solving Recurrences with the Substitution Method • Idea: Make a guess for the form of the solution and prove by induction. • Can be used to prove both upper bounds O() and lower bounds Ω(). • Let’s solve T (n) = 2T (n/2) + n using substitution – Guess T (n) ≤ cn log n for some constant c (that is, T (n) = O(n log n)) – Proof: ∗ Base case: we need to show that our guess holds for some base case (not necessarily n = 1, some small n is ok). Ok, since function constant for small constant n. ∗ Assume holds for n/2: T (n/2) ≤ c n log n (Question: Why not n − 1?) 2 2 Prove that holds for n: T (n) ≤ cn log n T (n) = 2T (n/2) + n n n ≤ 2(c log ) + n 2 2 n = cn log + n 2 = cn log n − cn log 2 + n = cn log n − cn + n So ok if c ≥ 1 • Similarly it can be shown that T (n) = Ω(n log n) Exercise! • Similarly it can be shown that T (n) = T ( Exercise! n 2 ) + T( n 2 ) + n is Θ(n lg n). • The hard part of the substitution method is often to make a good guess. How do we make a good (i.e. tight) guess??? Unfortunately, there’s no “recipe” for this one. Try