(20 POINTS) There are times when you can correctly guess an asymptotic bound as the solution of a recurrence, but the math may still not work in induction. As an example, given the recurrence T(n) = T(n/2) + T (n/2) + 1. We guess that the solution is O(n), and we try to show that T(n) cn for an appropriate choice of the constant c. Substituting our guess in the recurrence, we obtain:

T(n) c(n/2) + c(n/2) + 1

cn + 1

which does not imply T(n) cn for any choice of c.

In order to prove our original guess, i.e. the solution is O(n), we must make a stronger inductive hypothesis: Subtract a lower order term (which is d for this example) from our previous guess, such that the new guess becomes T(n) cn - d, where b 0 is constant. We now have

T(n) (cn/2 - d) + (cn/2 - d) + 1

cn 2d + 1

cn - d

For d 1, we have proven that T(n) is O(n).

Using the information provided above, now consider the recurrence relation T(n) = 4T(n / 3) + n to answer the following questions:

2.A.) (10 POINTS) Use the substitution method to show that the attempt to prove the guessed solution for T(n) is O(nlog34) fails. Please show your work. 2.8.) (10 POINTS) Now, try subtracting a lower order term (which is dn for this question) from the guess so that the substitution proof work, i.e. Tn) is O(nlog34) Also remember that solving recurrences will yield: Asymptotic tight bound "O", if the recurrence is in the form T(n) = at(n/b) + f(n) Asymptotic upper bound "O", if the recurrence is in the form T(n) SaT(n/b) + f(n) Asymptotic lower bound "0", if the recurrence is in the form T(n) 2 aT(n/b) + f(n)