Master Theorem & Recurrence Relations Exercises

b)
Let T(n) be defined recursively as follows:
T(11)= -11 and T(n)= 2T(Floor(n/2)+5) +n for all n≥12. Prove by induction on n that T(n)≤(n-10)log(n-10) -11 for all integers n≥11.

c)
Let T(n) be defined recursively as follows: T(n)=4T(n/2) + n² (note that for sufficiently small n, T(n) is bounded by a constant). Use the Master Theorem to solve this recurrence relation up to a constant factor.

d)
Same as part c) except this time T(n)=3T(n/2)+n.

b).
T(11) = - 11
T(n)=2*T(FLOOR(n/2)+5)+n, (∀) n ≥12.
We must prove using induction that T(n)≤(n-10)*log⁡〖(n-10)〗-11 (∀) n ≥11.
P(n): T(n)≤(n-10)*log⁡〖(n-10)〗-11 (∀) n ≥11....

This is only a preview of the solution. Please use the purchase button to see the entire solution