Consider the recurrence relation:

$T(n)=2T(\frac{n}{3})+n$ with $T(1)=3$

Suppose we begin to solve this by digging down.

$($a$)$ Fill in the first two steps when digging down.

$[6$ pts$]$

$($b$)$ Write down a general expression for the $k^{th}$ step. The box on the right should have a $[4$ pts$]$ sum which you don't need to evaluate.

$T(n)=$

$($c$)$ For which $k$ will we reach the base case?

$[2$ pts$]$

$k=$

Scratch Work; Not Graded: