Q3 30 Points Recurrences A 10 Points Given A Recurrence T N T N 1 T N 2 1 Please Draw The Recursion 1 (27.83 KiB) Viewed 23 times
Q3 30 Points Recurrences A 10 Points Given A Recurrence T N T N 1 T N 2 1 Please Draw The Recursion 2 (26.46 KiB) Viewed 23 times
Q3 30 Points Recurrences A 10 Points Given A Recurrence T N T N 1 T N 2 1 Please Draw The Recursion 3 (24.35 KiB) Viewed 23 times
• Q3(30 points): Recurrences (a) (10 points) Given a recurrence T(n) = T(n − 1) +T(n − 2) +1, please draw the recursion tree and derive a good upper bound and a good lower bound of T(n).
(b)(10 points) Given a recurrence T(n) = 3T(n − 1) +1, please use the substitution method to verify T(n) = 0(3¹). Hint: use the hypothesis T(n) ≤ c(3¹ − 1) for some c> 0.
(c) (10 points) Please solve the recurrence T(n) = 3T(n-1)+log n using the Master Method. Hint: try to transfer the equation to another form and then solve it.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!