-------------------------------------------------- * PS1 is due Monday in lecture! hopefully you've started on it. * Monday lecture: Master method. * Wednesday lecture: Divide-and-conquer. ------------------- How do you do mergesort? MERGESORT(A) : 1. divide A into two arrays of size |A|/2. [<- i ->|<- ii ->] 2. recursively MERGESORT() these subarrays. 3. merge the results. Running time: T(n) = 2T(n/2) + cn. T(1) = 1. a = 2, b = 2, f(n) = cn. n^log_b(a) = n^1 = n = Theta(f(n)). ==> T(n) = Theta(n log n), by the master method. (Right??) Great! But what if |A| is odd? Really: T(n) = T(floor(n/2)) + T(ceil(n/2)) + cn. Which case of the master method is this? None! Okay, here's one way to handle this. * Before we even start mergesorting, let's pad the array so that its length is a power of two. MERGESORT'(A): 1. Let k be the smallest integer so that n = |A| <= 2^k. 2. Let A' = [A infty infty ... infty] <-------------------> 2^k - n times 3. MERGESORT(A'). * Now, what's the running time of Mergesort'? Step 1 takes O(n + log n) = O(n) time. (Count n. The increment k until you're done.) Step 2 takes Theta(2^k - n) time. But notice: 2^k - n < n <=> 2^k < 2n <=> 2^(k-1) < n. By the choice of k, Theta(2^k - n) = O(n). Step 3 takes T(2^k) = Theta(2^k log 2^k) time. --> n log n = O(2^k log 2^k). n <= 2^k. For n_0 = 0, c = 1, we have that n log n <= 2^k log 2^k >= n log n. Done. --> n log n = Omega(2^k log 2^k). n >= 0.5 * 2^k. n log n <= (2^k)/2 log (2^k)/2 = 1/2(2^k log 2^k - 2^k) = 1/4(2^k log 2^k) - ((2^k)/2 - 1/4(2^k log 2^k)) <= 1/4(2^k log 2^k) whenever (2^k)/2 <= (2^k)/4 log(2^k) 2 <= log(2^k) 4 <= k 3 <= n. Choose n_0 = 3, c = 1/4. Done. ------------------- Basically, the thing that we just did with Mergesort can always be done. This is the _SLOPPINESS THEOREM_: THEOREM: If i) T(n), f(n) are monotonically increasing. ii) T(b^i) <= f(b^i) for all i >= 0 ("it works for exact powers") iii) f(n) = O(f(n/b)) ("polynomial growth" -- breaks for exponentials) then T(n) = O(f(n)). proof (omitted?): T(n) <= T(b^ceil(log_b n)) by (i) <= f(b^ceil(log_b n)) by (ii) <= cf(b^ceil(log_b n) / b) for n>n_0 (for some c, n_0) by (iii) <= cf(b^(ceil(log_b n)-1)) by third grade <= cf(b^(log_b n)) by (i) <= cf(n). -------------------- Another form of sloppiness: T(n) = T(n/2 + log(n)) + 1 The lower-order term in the recursive call basically doesn't matter. Still have to do some work, but generates the right guess. Figure out T'(n) = T'(n/2) + 1 = Theta(log n) as a guess. Then plug back in using substitution. Can require some creativity to prove, but it's usually the right answer. Here's a slightly harder example, with thanks to Matt Lepinski. [This wasn't covered during recitation.] T(n) = 2T(n/2 + sqrt(n)) + 1. Claim: T(n) = O(n). Proof: We'll show that T(n) <= cn - b sqrt(n) for appropriate constants b,c by induction on n. The base case is trivial. For the inductive case, T(n) = 2T(n/2 + sqrt(n)) + 1 <= cn + 2c sqrt(n) - 2b sqrt(n/2 + sqrt(n)) + 1 <= cn + 2c sqrt(n) - 2b sqrt(n/2) + sqrt(n) <= cn + 2c sqrt(n) - 2b sqrt(n/2) + sqrt(n) <= cn + sqrt(n) (2c - 2b/sqrt(2) + 1) <= cn + sqrt(n) (2c - sqrt(2)b + 1). This shows exactly what we wanted, so long as 2c - sqrt(2) b + 1 <= -b 2c + 1 <= (sqrt(2) - 1)b 2c + 1 / (sqrt(2) - 1) <= b which is true, e.g., for c = 1 and b = 5. Claim #2: T(n) = Omega(n). Proof: easy. T(n) = 2T(n/2 + sqrt(n)) + 1 <= 2T(n/2) + 1 = Omega(n). So T(n) = Theta(n). Just as we thought it would be. -------------------- You all remember the Master Method, right? Master Method: Let a>=1, b>=1 be constants. If T(n) = aT(n/b) + f(n) then 1) if f(n) = O(n^{log_b a} - \epsilon) for some eps>0 then T(n) = Theta(n^{\log_b a}) 2) if f(n) = Theta(n^{log_b a}) then T(n) = Theta(n^{\log_b a} log n). 2')if f(n) = Theta(n^{log_b a}log^k n) then T(n) = Theta(n^{\log_b a} log^(k+1) n). 3) if f(n) = Omega(n^{log_b a} + \epsilon) for some eps>0 then T(n) = Theta(f(n)) if af(n/b) <= cf(n) for some c<1 and all sufficiently large n. * Outline proof of case 2. --> Draw recursion tree. f(n) / | \ <-- branching factor: a f(n/b) ... f(n/b) height = log_b(n) # leaves = a^(log_b(n)) log_b(L) = log_b(n) log_b(a) = log_b(n^\log_b(a)) L = n^log_b(a). --> work at top level is n^log_b(a). work at second level is (n/b)^log_b(a) * a = (n^log_b(a) / a) * a etc. --> total work is n^log_b(a) per level; log_b(n) levels. --> Theta(n^log_b(a) log n). * Outline proof of case 1 [not covered in recitation]. --> work at any level L is a^L * f(n/b^L) << a^L (n/b^L)^log_b(a) = a^L n^log_b(a) / a^L = n^log_b(a). --> work at leaves is n^log_b(a). Asymptotically, all the work is at the leaves of the recursion tree. --------------------- Death by one million examples: * T(n) = 7T(n/2) + n^2. log_2 7 = 2.807, f(n) = O(n^2.807-eps). Case 1 ==> T(n) = Theta(n^2.807). * T(n) = 2T(n/4) + sqrt(n). log_4 2 = 0.5, f(n) = Theta(n^0.5). Case 2 ==> T(n) = Theta(sqrt(n) log n). * T(n) = T(3n/4) + n. log_(4/3) 1 = 0. f(n) = Omega(n^0+eps). Case 3 ==> T(n) = Theta(n). check regularity: af(n/b) <= cf(n) for some c<1 and all sufficiently large n. 3n/4 <= cn for some c<1? You bet. * T(n) = 16T(n/4) + n^2 log^2 n. log_4 16 = 2. f(n) = Theta(f(n) log^2 n). Case 2 ==> T(n) = Theta(n^2 log^3 n). * T(n) = 9T(n/3) + n^3. log_3 9 = 2. f(n) = Omega(n^2+eps). Case 3 ==> T(n) = Theta(n^3). (check regularity.) * T(n) = 27T(n/3) + cn^2. log_3 27 = 3, f(n) = O(n^3). Case 1 ==> T(n) = Theta(n^3). * T(n) = 4T(n/2) + cn^2. log_2 4 = 2, f(n) = Theta(n^2). Case 2 ==> T(n) = Theta(n^2 log n). * T(n) = 2T(n/3) + cn. log_3 2 = 0.631..., f(n) = Omega(n^0.631..). Case 3 ==> T(n) = Theta(n). (check regularity.) [tricky one follows] * T(n) = 2T(n/2) + n log n. log_2 2 = 1, f(n) = Omega(n^1). BUT! f(n) is NOT Omega(n^1+eps)! Master Method doesn't apply. [footnote added post-recitation: the master method as stated in the book doesn't work for this. however, the version from lecture does cover this case. If you instead consider, e.g., T(n) = 2T(n/2) + n log log n then neither version applies.] Still solveable, but takes more work. Here's a sketch of how it works [ not covered in recitation ] look at the recursion tree. root input size n, work n log n. / \ x x input size n/2, work 2 * n/2 log n/2 / \ / \ = n log n/2 x x x x input size n/4, work 4 * n/4 log n/4 = n log n/4 etc. so the total work is \sum_{i=1}^log(n) n log (n/2^i) = n \sum_{i=1}^log(n) (log n - 2^i) = n (log^2 n - \sum_{i=1}^logn log(2^i)) = n (log^2 n - \sum_{i=1}^logn i) ~= n (log^2 n - (log^2 n)/2) = Theta(n log^2 n). * T(n) = 2T(n/2) + n!. log_2 2 = 1, f(n) = Omega(n). ----> n! DOES NOT violates regularity, DESPITE WHAT WAS SAID IN 11:00A RECITATION. The correct intuition for the regularity condition is that f() has to grow sufficiently REGULARLY. (Duh.) Bill Thies worked out an example in which the regularity condition breaks in the master method -- thanks, Bill! Here it is: T(n) = T(n/2) + n(sin(n - pi/2) + 2) We fall into case 3, since log_b(a)=log_2(1)=0 and f(n) = Omega(n). The regularity condition is af(n/b) <= cf(n) for some constant c<=1 and all sufficiently large n. That is, f(n/2) <= cf(n) for some c<1. So: (n/2) (sin(n/2 - pi/2) + 2) <= c n (sin(n-pi/2) + 2) (1/2) (sin(n/2 - pi/2) + 2) <= c (sin(n-pi/2) + 2) c >= [sin(n/2 - pi/2) + 2] / [2 (sin(n-pi/2) + 2)] for some c<1 and all sufficiently large n. But this cannot be satisfied. Choose, for instance, n = 2*pi*k, for an arbitrarily large odd number k. Then c >= [sin(pi (k - 1/2)) + 2] / [2 (sin(pi(2k-1/2) + 2)] sin(pi(k-1/2)) = sin(pi/2) = 1 sin(pi(2k-1/2)) = sin(3pi/2) = -1 c >= (1 + 2) / 2(-1 + 2) = 3/2 which violates c < 1. <---- CHANGING VARIABLES: * T(n) = 2T(sqrt(n)) + log n. What case? None; not even the right form. Draw recursion tree. n n^1/2 n^1/4 n^1/8 ... how high is the tree? Well, how big is h before n^{2^-h} = Theta(1)? 2^-h log n = Theta(1) log n = c 2^h c log log n = h. height is log log n. work per level? log(n) at top. 2 * log(sqrt(n)) at second = 2 * (log n) /2 = log n. maybe log n each? let's prove it. Claim: T(n) <= c log n log log n. Proof by induction on n. base case: check. inductive: T(n) = 2 T(sqrt(n)) + log n <= 2 log n^0.5 log log n^0.5 + log n = log n (log log n^0.5 + 1) = log n (log (0.5 log n) + log 2) = log n (log log n). Okay, but there was an easier way! Let's change variables. T(n) = T(sqrt(n)) + log n. Let m = log(n). S(m) = T(2^m). So n = 2^m. sqrt(n) = 2^(m/2). T(2^m) = 2T(2^(m/2)) + m S(m) = 2S(m/2) + m = Theta(m log m) T(n) = T(2^m) = S(m) = Theta(m log m) = Theta(log n log log n).