Consider the recurrence T (n) = 3 T (n/2) + n.

• Use the recursion tree method to guess an asymptotic upper bound for T (n). Show your work.

Prove the correctness of your guess by induction. Assume that values of n are powers of 2.