For the recurrence T $($n$)=2$T $($n$/3)+$ n do the following:

$1.$ Draw the recursion tree and use it to calculate an asymptotically tight bound on T $($n$).$ That is find

an f $($n$)$ in each case such that T $($n$)=\backslash$Theta $($f $($n$)).$ You don$$t need to provide a formal proof for this

step.

$2.$ Prove this Big$-$Theta relationship via induction.

$3.$ Finally, solve the recurrence $($upto big$-$Theta$)$ using the Master theorem.

You can assume T $(1)=1$ and you can ignore issues regarding the inputs to T possibly being fractions

at any point.