Answer using the substitution/iteration method ONLY i.e. substituting in n/2, n/4, ... and so on into T(n) to find the pattern and solve the question.

e constant, then prove that the recurrence k is a nonnegativ T(n) = n= 3T(n/2) + kn n > 1 (3.17) as the following solution (for n a power of 2): T(n) = 3km log23-2km (3.18) roof that shows that the recurrence relation T(n) = mT(n/2) 4. G Han2 is satisfied by T(n) = O(nlog m) for m > 4