Here is the answer to number 1.) if this helps. Consider the following recurrenc
ID: 3916209 • Letter: H
Question
Here is the answer to number 1.) if this helps.
Consider the following recurrence T(n): if n 1 T(n)- (5 points) 1. Draw the first six levels of the recursion tree by drawing all recursive calls of the same size on the same level. Make sure on each level you indicate the size of the recursive call and the number of recursive calls. (5 points) 2. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion tree. (5 points) 3. Give a function g(n) and show it is an upper bound on the sum. (5 points) 4. State and prove by induction a theorem showing T(n) EOgn) (5 points) 5. State and prove by induction a theorem showing T(n) e Q(g(nExplanation / Answer
proof using induction:
Induction proofs have four steps:
(1) Thing you want to prove
(2)Beginning step (usually "let n = 1")
(3) Assumption step ("let n = k"), and
(4) Induction step ("let n = k + 1").
To prove: For all n > 1, the running time of T(n) is n log n time, i.e., T(n) ? n log n + n.
Proof by induction on n
Base Case: n = 1: T(1) = 1 = 1 log 1 + 1
Induction Hypothesis: Assume that for arbitrary n, T(n) ? n log n + n
Prove T(n+1) ? (n+1) (log (n+1)) + (n+1)
T(n+1) = 2*T((n+1)/2) + Tmerge(n+1)
? ((n+1) (log (n+1)/2)) + Tmerge(n+1) By Induction Hypothesis
? 2((n+1)/2 (log (n+1)/2) + (n+1)/2) + (n+1)
? (n+1) log (n+1) + (n+1)
Thus, we can conclude that the running time of T(n) is O(n log n).