=========================================================================== CSC 236 Tutorial Solutions for Week 4 Winter 2012 =========================================================================== 1. Consider the function T(n) defined by the following recurrence: { 1 if n = 1 T(n) = { { 1 + T(ceil(n/2)) if n > 1 Prove that T(n) is in \Theta(lg n). (a) T(n) (- \Omega(lg n): - Scratch work: { This one was done in lecture, so it's here for review only. } Q: What do we need to figure out? A: Values of constants B, c > 0 such that T(n) >= c lg(n) for all n >= B. Q: How can we find these values? A: Imagine the final proof and see what we need for the inductive step and the base case. In the inductive step, we will have T(n) = 1 + T(ceil(n/2)) and use the I.H. to say that this is >= 1 + c lg(ceil(n/2)) Now we work with this to simplify it: >= 1 + c lg(n/2) (because ceil(n/2) >= n/2 and lg is an increasing function) >= 1 + c (lg(n) - lg(2)) (properties of lg) >= 1 + c lg(n) - c Remember our goal: T(n) >= c lg(n). So set the inequality and solve for c! c lg(n) + (1 - c) >= c lg(n) <=> 1 >= c Q: Are we done? A: Almost: we should double-check the base case to be sure it works. T(1) = 1 >= 0 = lg(1), so we're good. - Proof that T(n) >= lg(n) for all n >= 1, by complete induction. Base Case: T(1) = 1 >= 0 = lg(1). Ind. Hyp.: Let k > 1 and suppose T(j) >= lg(j) for 1 <= j < k. Ind. Step: To prove T(k) >= lg(k), consider T(k) = 1 + T(ceil(k/2)) (by recurrence for T, since k > 1) >= 1 + lg(ceil(k/2)) (by IH, since 1 <= ceil(k/2) < k for k > 1) >= 1 + (lg(k) - lg(2)) (since ceil(x) >= x so lg(ceil(x)) >= lg(x) for all x) >= lg(k). Hence, by induction, T(n) >= lg(n) for all n >= 1. (b) T(n) (- O(lg n): - Scratch work: . As above, start with inductive step to find constraints on c. T(n) = 1 + T(ceil(n/2)) <= 1 + c lg(ceil(n/2)) (by the I.H.) Problem 1: we want ceil(n/2) <= something. Q: What is that something? A: ceil(n/2) <= n/2 + 1 Let's continue: <= 1 + c lg(n/2 + 1) Problem 2: there is no obvious way to get rid of that "+1" inside the log... TRICK! ceil(n/2) <= (n+1)/2 so ceil(n/2) - 1 <= (n+1)/2 - 1 = (n-1)/2. { Don't expect them to come up with this! It's not obvious. } Q: How does that help exactly? A: Instead of proving T(n) <= c lg(n), we will prove T(n) <= c lg(n-1), and the extra "-1" will carry through. T(n) = 1 + T(ceil(n/2)) <= 1 + c lg(ceil(n/2) - 1) <= 1 + c lg((n+1)/2 - 1) <= 1 + c lg((n-1)/2) <= 1 + c (lg(n-1) - lg(2)) <= c lg(n-1) + (1 - c) As before, this is <= c lg(n-1) iff 1 <= c so we can pick c = 1. Q: Are we done? A: No: we should check the base case to make sure it works. T(1) = 1 <= lg(1-1)... Problem 1: lg(0) is undefined! Q: Does this mean it won't work? A: Yes and no: remember we're trying to prove T(n) is O(lg n), so all we care about are values of n "large enough". In other words, we can ignore n = 1 and just start with n = 2. T(2) = 1 + T(ceil(2/2)) = 1 + T(1) = 2 lg(2-1) = lg(1) = 0 Problem 2: T(2) is not <= lg(2-1). Q: Great, this keeps getting better and better! A: That's not a question... Seriously, don't panic: this is just a minor setback. We can just change our bound slightly to fix this: let see if we can prove T(n) <= lg(n-1) + 2 instead! Base case: T(2) = 2 <= lg(2-1) + 2. Q: But wait, what about the induction step? A: Right, we should double-check it as well. T(n) = 1 + T(ceil(n/2)) <= 1 + lg(ceil(n/2) - 1) + 2 <= 1 + lg(n-1) - 1 + 2 Q: So everything works out fine, right? A: Not so fast! In order to apply I.H. in the induction step, we need argument ceil(n/2) to be < n and >= base case-- and our base case is now 2. Q: So what's the problem? A: Actually, in this case, there is none: if n > 2, then ceil(n/2) is >= 2 and < n. - Proof that T(n) <= lg(n - 1) + 2 for all n >= 2, by complete induction. Base Case: T(2) = 1 + T(ceil(2/2)) = 1 + 1 = 2 <= 0 + 2 = lg(1) + 2. Ind. Hyp.: Let n > 2 and suppose T(j) <= lg(j-1) + 2 for all 2 <= j < n. Ind. Step: Consider T(n) = 1 + T(ceil(n/2)) (by recurrence for T, since n > 2) <= 1 + lg(ceil(n/2)-1) + 2 (by IH, since 2 <= ceil(n/2) < n for n > 2) <= 1 + lg((n-1)/2) + 2 (since ceil(n/2)-1 <= (n+1)/2-1 = (n-1)/2) <= 1 + (lg(n-1) - lg(2)) + 2 <= lg(n-1) + 2. Hence, by induction, T(n) <= lg(n-1) + 2 for all n >= 2. Since lg(n-1) <= lg(n), T(n) (- O(lg n). { In the unlikely event you have any time left, feel free to solve the following recurrence with them: go through repeated substitution and then do a formal proof of the guess. This one is nice because it gets them to work with sums of powers of 2, and you can mention that an expression for T(n) that involves a sum (or a "...") is not really closed-form and still needs work. { 1 if n = 1, T(1) = { { 2 T(n-1) + 1 if n > 1. }