Q5

You want to show that the solution of T(n) = 4T(n/2) + n

is O(n²), using the substitution method. Unfortunately, if you

simply recursively plug in Cn² to try to make the method go

through, it doesn't work: on the left side of the inequality you

are trying to prove you are left with an extra term, so the left

side isn't the right side. The extra term is

However, you can make the proof work by modifying the

induction. Instead of proving it is < Cn², instead, you prove

that it is ≤ Cn² - Dn. The smallest value of D that will work

is

(Once you prove that T(n) ≤ Cn² - Dn, it is easy enough to

show that that is € 0(n²).)