Exercise 4.3-6* Show that the solution to T(n) = 2T( n / 2 17 ) + n is O( n lg n ) Solution: Assume T(n) = 1 if n ≤ 34 Let n0 = 35. Base case: T(35) = 1 + 35 ≤ c 34 lg (34) hold. To show that T(n) = O(n lg n), it is enough to show that T(n) < cn lg n First assume (inductive hypothesis) that T(n) < cn lg n, for all n ≤ 35, 36, …, k Therefore, T( n / 2 ) ≤ c( n / 2 17 ) lg( n / 2 + 17) Then show that the inductive hypothesis is true also for n = k + 1: T(n) = 2T( n / 2 17 ) + n ≤ 2c( n / 2 17 ) lg( n / 2 + 17) + n ≤ c(n + 34) lg( /2 + 17) + n ≤ c(n + 34) lg n + n = cn lg (n) + 34 lg (n) + n = O(n lgn) Exercise 4.3-8 Using the master method in Section 4.5, you can show that the solution to the recurrence T(n) = 4T(n/2)+n is T(n)=Θ(n2). Show that a substitution proof with the assumption T(n) ≤ cn2 fails. Then show how to subtract off a lower-order term to make the substitution proof work. Solution: If we guess T(n) ≤ cn2 T(n) ≤ 4c(n/2)2 +n ≤ cn2+n => This is not equal to cn2 Now we guess T(n)≤cn2−n T(n) ≤ 4(c(n/2)2−n/2)+n ≤ cn2−2n+n ≤ cn2−n => exact equal to our assumption. 4.4-6 Argue that the solution to the recurrence T(n) = T(n/3) + T(2n/3) + cn, where c is a constant, is Ω(n lg n) by appealing to the recursion tree. Solution: Note that each layer of the recursion tree totally cost cn. Layer 0: cn Layer 1: c(n/3) + c(2n/3) = cn Layer 2: c(n/9) + c(2n/9) + c(2n/9) + c(4n/9) = cn Because the recursion tree is unbalanced, the depth varies. To show T(n) = Ω(n lg n) is to find a lower bound, so we need to consider the shortest path first. It is trivial that the shortest path from root to a leaf is cn→ /3 → /9 → /27 →…→1. The height k is given by (1/3) ≤ 1, meaning cn ≤ 3 and k ≥ lg3 cn. Then we have T(n)≥ cn lg3 cn =cn( lg n +lg c)/lg 3≥(c/lg 3) n lg n, which implies T(n) =Ω(n lg n).

© Copyright 2021 Paperzz