1CISC320, F05, Lec3, Liao 1CISC 320 Introduction to AlgorithmsFall 2005Lecture 3Recurrences and Master theoremCISC320, F05, Lec3, Liao2General scheme for time complexity analysis1. For a sequence of blocks, add up the cost of individual blocks1. For a loop, the worst case = the loop range times the cost of a single iteration2. With alternation, take the cost of the most costly branch3. If recursive procedure called, add T(n’), where n’ is the size at call. CISC320, F05, Lec3, Liao3Recursion for computationA computation model is Turing complete when it can compute everything that can be computed by a Turing machine. Pragmatically, a model (or a language) is Turing complete if it can do sequence branch repetition (either as loop or as recursion)Recursion is as powerful as iteration in establishing a Turing complete model.  is proof-friendly for proving correctness of algorithms. (Thus promoted in functional programming languages, such as ML). Why? (Free of “Computing by Side Effect” problems using iterations) is also efficient. Myth: Loop is much faster than recursion  Truth: recursion can be as efficient as iteration. Note: any algorithm using recursion can be converted to using iterations, and vice versa.CISC320, F05, Lec3, Liao4Iterations can be converted as recursionsFor example, Sequential Search can be implemented recursivelyint seqSearchRec(int[] E, int m, int num, int K)int ans;1 if (m >= num) 2 ans = -1;3 else if (E[m] == K)4 ans = m;5 else6 ans = seqSearchRec(E, m+1, num, K);7 return ans;CISC320, F05, Lec3, Liao5For example, the recursive Sequential Search can be analyzed using this schemeint seqSearchRec(int[] E, int m, int num, int K)int ans;1 if (m >= num) 2 ans = -1;3 else if (E[m] == K)4 ans = m;5 else6 ans = seqSearchRec(E, m+1, num, K);7 return ans;Let n = num –m as the initial sizeT(n) = 1 + max(0, 1+ max(0, T(num-(m+1)))) + 0 = T(n-1) + 2Line1 Line2 Line 3 Line4 Line6Line7CISC320, F05, Lec3, Liao6Divide-and-ConquerE.g., Binary search of an ordered array. Modify the seqSearchRec to do binary search. If the recursive implementation of sequential search is superficial, a recursive implementation of binary search is a real convenience (as compared to a loop based implementation).T(n) = T(n/2) + Θ(1).In general, the cost of solving a problem of size n is shared by the cost of a subproblems of size n/b, plus non-recursive overhead cost f(n):T(n) = a T(n/b) + f(n)This is a recurrence equation. How to evaluate the cost T(n)?2CISC320, F05, Lec3, Liao7Recursion-tree methodT(n) = T(n/2) + T(n/2) + nT(n) nT(n/2) n/2 T(n/2) n/2T(n/4) n/4 T(n/4) n/4 T(n/4) n/4 T(n/4) n/4nnn…lg(n)(+n lg(n)row-sum or per-level costExample:CISC320, F05, Lec3, Liao8Observations of recursion-tree method1. T(n) = the sum of the nonrecursive costs of all nodes in the tree, which is the sum of the per-level costs at all levels;2. Depth of the tree is D = log bn;3. Number of leaves is approximately L = a D= nEwhere E = log ba;4. If the per-level costs remain about constant at all depth, then T(n) ∈Θ(f(n) log(n)).5. If the per-level costs grow fast, the cost at the leaves would dominate, therefore T(n) ∈Θ(nE);6. If the per-level costs decrease fast, the cost at the root would dominate, therefore T(n) ∈Θ(f(n));7. And more formally, CISC320, F05, Lec3, Liao9The Master theorem (Theorem 4.1) The recurrence equation T(n) = a T(n/b) + f(n), where a ≥ 1, b > 1, and n/b interpreted as either ⎡n/b⎤ or ⎣n/b⎦. Then T(n) can be bounded asymptotically as follows:1. If f(n) = O(nE-ε) for constant ε> 0, then T(n) = Θ(nE) where E = log ba, called critical exponent. (Note: this means nEis polynomially faster than f(n).)2. If f(n) = Θ(nE), then T(n) = Θ(f(n) log(n)).3. If f(n) = Ω(nE+ε) for ε> 0, and if af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n, then T(n) = Θ(f(n)). (Note: this means f(n) is polynomially faster than nE.)CISC320, F05, Lec3, Liao10Example 1T(n) = 7T(n/2) + n2 1. Recognize a, b, and f(n):a = 7, b = 2, and f(n) = n2 2. Compute E = log ba = lg(7)3. Compare f(n) and nEasymptoticallyf(n) = nlg7+(2-lg7) = nlg7 – 0.8 = O(nE-0.8)4. Apply appropriate case of Master Theoremcase 1 applies: T(n) = Θ(nlg7 )CISC320, F05, Lec3, Liao11Example 2T(n) = 4T(n/2) + n2 lg(n) 1. Recognize a, b, and f(n):a = 4, b = 2, and f(n) = n2lg(n) 2. Compute E = log ba = lg(4) = 23. Compare f(n) and nEasymptoticallyf(n)/ nE= n2lg(n) / n2 = lg(n)4. Determine appropriate case of Master Theorem and applycase 1 : f(n)/ nE= lg(n) =? O(n-ε) for some ε > 0 NOcase 2 : f(n)/ nE= lg(n) =? Θ(1) NOcase 3 : f(n)/ nE= lg(n) =? Ω(nε) for some ε > 0 NONote: lg(x) is faster than Θ(1) but slower than xεfor any ε > 0 (Exercise).Lesson: There are gaps between cases in Master Theorem, therefore Master Theorem does not cover all recurrence equations of that form.CISC320, F05, Lec3, Liao12Example 3 T(n) n2T(n/4)(n/4)2T(n/2)(n/2)2T(n/16) (n/16)2T(n/8) (n/8)2T(n/8) (n/8)2T(n/4) (n/4)2n2(5/16)n2(25/256)n2…lg(n)+Exercise: T(n) = n2(1+ 5/16 + (5/16)2+ …) ≤ (16/11) n2= Θ(n2) T(n) = T(n/4) + T(n/2) + n2row-sum3CISC320, F05, Lec3, Liao13Substitution method Make a guess Substitute it into the recurrence Prove the recurrence hold by mathematical inductionExample: T(n) = T(n/4) + T(n/2) + n2.From decision tree method, we have a good guess that T(n) =O(n2). Let T(n) ≤ cn2, where c is a suitable positive constant.Plug it into the RHS of the recurrence.T(n) ≤ c (n/4)2+ c(n/2)2+ n2= (c/16 + c/4 +1) n2 ≤ cn2, when c ≥ 16/5CISC320, F05, Lec3, Liao14Induction ProofsA mechanic procedure with mainly 3 stepsStep 1: prove base case(s), e.g., n=0.Step 2: assume the goal is true for arbitrary n, say n=k.Step 3: then prove it is also true for n=k+1.CISC320, F05, Lec3, Liao15Example: Σi=1ni = n(n+1)/2Base case n = 1LHS = 1 and RHS = 1(1+1)/2 = 1Note: we can do this manually for n =2, 3, …Let’s assume it holds for arbitrary n ≥ 1, we now prove it also holds for n+1.LHS(n+1) = Σi=1n+1i = (Σi=1ni) + (n+1)= n(n+1)/2 +(n+1)= [n(n+1) + 2(n+1)]/2= (n+1)[n+2]/2= RHS(n+1)Since we have proved manually it is true when n=1. Now we know if it is true for n=1 it must be true for n =2, and if it is true for n=2 it must be true for n=3, and on and on. Note: such a procedure is like to unravel a recursive call in a reversed order, i.e., from base case to more general