PROBLEM 6 (10 points) I claim that merge-sort is actually a linear time algorithm -- i.e., faster than (NlogN) . Below is a sketch of my "proof" that the runtime of merge-sort is actually O(n) For simplicity, I am only proving my claim for powers of 2 (so I don't have to worry about floors and ceilings). We already know that the runtime of merge-sort is described by the recurrence relatiorn T(1) = 1 T(n)=2T(n/2)+ n for n >1 I want to show that T(n)=O(n). To make this Big-Oh claim, I will show that that T(n) Scn for all n2 1 and some constant c BASE-CASE: T(l)-Scx 1 exists! as long as c > 1 clearly such a constant INDUCTIVE HYPOTHESIS: Assume the claim holds for powers of 2_Less than k where k is itself a power of 2: k=2' where i > 0 (and so k > 2). Notice that this covers T(k/2) Now I have to prove the claim holds at k. PROOF: T(k) 2T(k/2) +k from recurrence relation and k> 1 by I.H. applied to T(k/2) algebra algebra because (c+) is a constant and S 2c(k/2) = (e+ 1)k = 0(k) a constant times k is still O(k), since we know that " constants don't matter"! Q.E.D. PROBLEM 6 (10 points) I claim that merge-sort is actually a linear time algorithm -- i.e., faster than (NlogN) . Below is a sketch of my "proof" that the runtime of merge-sort is actually O(n) For simplicity, I am only proving my claim for powers of 2 (so I don't have to worry about floors and ceilings). We already know that the runtime of merge-sort is described by the recurrence relatiorn T(1) = 1 T(n)=2T(n/2)+ n for n >1 I want to show that T(n)=O(n). To make this Big-Oh claim, I will show that that T(n) Scn for all n2 1 and some constant c BASE-CASE: T(l)-Scx 1 exists! as long as c > 1 clearly such a constant INDUCTIVE HYPOTHESIS: Assume the claim holds for powers of 2_Less than k where k is itself a power of 2: k=2' where i > 0 (and so k > 2). Notice that this covers T(k/2) Now I have to prove the claim holds at k. PROOF: T(k) 2T(k/2) +k from recurrence relation and k> 1 by I.H. applied to T(k/2) algebra algebra because (c+) is a constant and S 2c(k/2) = (e+ 1)k = 0(k) a constant times k is still O(k), since we know that " constants don't matter"! Q.E.D