The solution to the recurrence T(n) = 4T(n/2) + n turns out to be 7(n) =...

Transcribed Image Text:

The solution to the recurrence T(n) = 4T(n/2) + n turns out to be 7(n) = e(n). Show that a substitution proof with the assumption 7(n) ≤ cn fails. Then show how to subtract a lower-order term to make a substitution proof work. Question 2) [2 points] Sketch the recursion tree to generate a good guess for the asymptotic upper bound on its solution. Then use the substitution method to verify your answer. T(n) = 4T(n/3) + n Question 3) [2 points] Use the master theorem to give an asymptotic upper bound for the following recurrences. Tell me the values of a, b, the case from the master theorem that applies, and the asymptotic upper bound. 3a) T(n) = 2T (n/4) + n 3b) T(n) = 4T (n/3) + nlgn Question 4) [3 points] Can the master method be applied to the recurrence... T(n) = 4T (n/2) + n²lgn Why or why not? Give an asymptotic upper bound for this recurrence and prove that it is in fact an asymptotic upper bound using the substitution method. The solution to the recurrence T(n) = 4T(n/2) + n turns out to be 7(n) = e(n). Show that a substitution proof with the assumption 7(n) ≤ cn fails. Then show how to subtract a lower-order term to make a substitution proof work. Question 2) [2 points] Sketch the recursion tree to generate a good guess for the asymptotic upper bound on its solution. Then use the substitution method to verify your answer. T(n) = 4T(n/3) + n Question 3) [2 points] Use the master theorem to give an asymptotic upper bound for the following recurrences. Tell me the values of a, b, the case from the master theorem that applies, and the asymptotic upper bound. 3a) T(n) = 2T (n/4) + n 3b) T(n) = 4T (n/3) + nlgn Question 4) [3 points] Can the master method be applied to the recurrence... T(n) = 4T (n/2) + n²lgn Why or why not? Give an asymptotic upper bound for this recurrence and prove that it is in fact an asymptotic upper bound using the substitution method.

Answer rating: 100% (QA)

Question 1 Part 1 Substitution Proof Failure with Assumption Tn cn Assuming Tn cn we can try to prov... View the full answer