Use substitution as directed below to solve T(n)={4T(n/3)+n1ifn3ifn2 It is strongly recommended that you read pages 92-93 "A trick of the trade" (page 85-86 "Subtleties" in the 3rd edition) in the CLRS textbook before trying this! (a) First, use the result from the Master Method in Problem 2 as your "guess" and inductive assumption. We will do this without and c : just use the algebraic portion. Take the proof up to where it fails and say where and why it fails. (See steps below.) (b) Redo the proof, but subtracting dn from the guess to construct a new guess. Remember, d is just some constant, so you should determine what d is equal to. (c) Redo the proof by guessing the value of T(n) with the specific value of d that you computed in part (b) above. If you computed T(n) correctly, your proof should succeed. As a reminder, to do a proof by substitution you: 1. Write the definition T(n)=4T(n/3)+n 2. Replace the T(n/3) with your "guess" instantiated for n/3 (you can do that by the inductive hypothesis because n/3 is smaller than n ). 3. Operating only on the right hand side of the equation, transform that side into the exact form of your "guess". 4. Determine any constraints on the constants involved. 5. Show the base case holds. For this problem you don't have to worry about the base case. We want you to focus on how to do the other steps