Use the recursion tree method to guess an asymptotic upper bound..

for 3.B, ASSUME BASE CASE T(1) = 1

Problem 3. Consider the recurrence T(n) = 3. T(n/2) +n. Problem 3.a. (3 points) Use the recursion tree method to guess an asymptotic upper bound for T(n). Show your work. Problem 3.b. (3 points) Prove the correctness of your guess by induction. Assume that values of n are powers of 2