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.

**Subject Computer Science Discrete Math**