Use the substitution method to show that the solution of T(n) = T(n - 1) + n is O(n^2). Using the master method, you can show that the solution to the recurrence T(n) = 4T(n/3) + n is T(n) = Theta (n^log_3 4). Show that a substitution proof with the assumption T(n) lessthanorequalto cn^log_3 4 fails. Then show how to subtract off a lower-order term to make a substitution proof work. Use a recursion tree to give an asymptotical upper-bound to the recurrence T(n) = T(alpha n) + T((l - alpha)n) + cn, where a is a constant in the range 0 0 is also a constant. Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n lessthanorequalto 2. Make your bounds as tight as possible, unless noted, and justify your answers. T(n) = 2T(n/2) + n^4. T(n) = T(7n/10) + n. T(n) = 16T(n/4) + n^2. T(n) = 7T(n/3) + n^2. T(n) = 7T(n/2) + n^2. T(n) = 2T(n/4) + squareroot n. T(n) = T(n - 2)+n^2. Use the substitution method to show that the solution of T(n) = T(n - 1) + n is O(n^2). Using the master method, you can show that the solution to the recurrence T(n) = 4T(n/3) + n is T(n) = Theta (n^log_3 4). Show that a substitution proof with the assumption T(n) lessthanorequalto cn^log_3 4 fails. Then show how to subtract off a lower-order term to make a substitution proof work. Use a recursion tree to give an asymptotical upper-bound to the recurrence T(n) = T(alpha n) + T((l - alpha)n) + cn, where a is a constant in the range 0 0 is also a constant. Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n lessthanorequalto 2. Make your bounds as tight as possible, unless noted, and justify your answers. T(n) = 2T(n/2) + n^4. T(n) = T(7n/10) + n. T(n) = 16T(n/4) + n^2. T(n) = 7T(n/3) + n^2. T(n) = 7T(n/2) + n^2. T(n) = 2T(n/4) + squareroot n. T(n) = T(n - 2)+n^2