c Balaji Raghavachari 23 Algorithm Design and Analysis✬✫✩✪Master methodMethod for solving most recurrences that occur when usingdivide and conquer (proved using iteration method):T (n) = aT (n/b) + f(n), where a ≥ 1, b > 1 are constants1. If f(n) = O(n(logba)−ǫ) for some constant ǫ > 0, thenT (n) = Θ(n(logba)).2. If f(n) = Θ(n(logba)), then T (n) = Θ(n(logba)lg n).3. If f(n) = Ω(n(logba)+ǫ) for some constant ǫ > 0, a nd ifaf(n/b) ≤ cf(n) for some constant c < 1 and allsufficiently large n, then T (n) = Θ(f (n)).c Balaji Raghavachari 24 Algorithm Design and Analysis✬✫✩✪Application of the master methodExercise 4.3-1 (page 75):1. T (n) = 4T (n/2) + n.a = 4, b = 2, n(logba)= n2, f(n) = n = O(n2−ǫ) for 0 ≤ ǫ ≤ 1.From Case 1, T (n) = Θ(n2).2. T (n) = 4T (n/2) + n2.a = 4, b = 2, n(logba)= n2, f(n) = n2.From Case 2, T (n) = Θ(n2lg n).3. T (n) = 4T (n/2) + n3.a = 4, b = 2, n(logba)= n2, f(n) = n3= Ω(n2+ǫ) for 0 ≤ ǫ ≤ 1.Also, af(n/b) = 4(n/2)3= n3/2 ≤ cf(n) for any12≤ c < 1.From Case 3, T (n) = Θ(n3).c Balaji Raghavachari 25 Algorithm Design and Analysis✬✫✩✪Simpler Master Method: when f(n) = cnk• Consider the special case when the recurrence isT (n) = aT (n/b) + cnk:1. Case 1: If k < logba, then T (n) = Θ(nlogba)2. Case 2: If k = logba, thenT (n) = Θ(nlogbalog n) = Θ(nklog n)3. Case 3: If k > logba, then T (n) = Θ(nk)c Balaji Raghavachari 26 Algorithm Design and Analysis✬✫✩✪When Master method failsRecurrences for which t he M aster method does not apply:• Tower of Hanoi: T (n) = 2T (n − 1) + 1 (not the rightform). Use substitution method: T (n) = O(2n).• Median problem: T (n) = T (n/5) + T (7n/10) + n (not theright form; problem sizes are nonuniform). Substitutionmethod can be used to prove that T ( n) = O(n).• Sorting network design: T (n) = 2T (n/2) + n log n: in thiscase a = 2, b = 2, f(n) = n log n, nlogba= n. Here, n issmaller than n log n, but not polynomially smaller. Usesubstitution method: T (n) = O(n log2n).c Balaji Raghavachari 32 Algorithm Design and Analysis✬✫✩✪Merge algorithmAlgorithm Merge(A, p, q, r)1: Copy A[p..q] into L[1..q − p + 1]2: Copy A[q + 1..r] into R[1..r − q]3: Set sentinels L[q − p] = R[r − q + 1] = ∞4: i ← 1; j ← 15: for k ← p to r do6: if L[i] ≤ R [j] then7: A[k] ← L[i]; i ← i + 18: else9: A[k] ← R[j]; j ← j + 1c Balaji Raghavachari 33 Algorithm Design and Analysis✬✫✩✪Correctness of Merge• Loop Invariant: When loop (k) is entered, A[p..k − 1]contains the k − p smallest elements of L and R, insorted order. Moreover, L[i] and R[j] are the smallestelements of L, R that have not been copied into A.• Initialization: When entering for the first time,i = 1, j = 1, k = p (lines 4,5). So, A[p.. k − 1] is an emptyarray, satisfying the first part of the L.I. Also L[1] andR[1] have the smallest elements of L and R repectively,because L and R are sorted.• Maintenance: when the loop is entered for k , by theL.I., A[p..k − 1] contains the k − p smallest elements, insorted order. On enteri ng the loop, we compare L[i]and R[j] (line 6):c Balaji Raghavachari 34 Algorithm Design and Analysis✬✫✩✪1. If L[i] ≤ R[j], then L[i] is the k − p + 1thsmallest elementof L and R because, (i) L[i] ≤ L[i′], for i < i′, (ii)L[i] ≤ R[j] ≤ R[j′], for j < j′. The algori thm copies L[i]to A[k] (line 7). So now, A[p..k] contain the k − p + 1smallest elements of L and R, in sorted order (first partof L.I. for next iteration of loop). Then i isincremented by 1 (line 7). L[i..n1] and R[j.. n2] are stillunprocessed, a nd since they are sorted, L[i] and R[j] arethe smallest elements of L and R that have not beencopied back to A (rest of L.I.).2. Otherwise, L[i] > R[j]. This case is symme tric to Case1, with roles of {L, i} and {R, j} reversed.• Termination: When loop finishes, k = r + 1. By L.I.,A[p..k − 1] = A[p..r] contains the r − p + 1 elements of Land R, in sorted order. Since L and R had r − p + 1elements that are not ∞, none of these is the sentinelelement. So, Merge is correct.c Balaji Raghavachari 35 Algorithm Design and Analysis✬✫✩✪Correctness of Merge SortProof by induction on the problem size, n = r − p + 1. Whenn ≤ 1, no work is needed to sort A[p..r], since it is alreadysorted. Let the al gorithm sort correctly on arrays with fewerthan n elements. Consider n. By the property of floors,q = ⌊r+p2⌋ < r. Therefore A[p..q] has fewer than n elements(because A[r] i s not in it), and A[q + 1..r] has fewer than nelements (because A[q] is not in it). By the I.H., thealgorithm correctly sorts A[p..q] and A[q + 1..r]. We justshowed that given sorted arrays, Merge ( A, p, q, r) correctlyoutputs a sorted array A[p..r]. Ther efore the M e rge sortalgorithm works
View Full Document
Unlocking...