Consider the recurrence $T(n)=2*T(|$~$\frac{n}{3}$~$|)+n$ when $n2,$ with boundary condition $T(1)=1.$

$($a$)(10$ points$)$ Use the recursion tree method to form a guess for an appropriate function $f(n)$ such that $T(n)=O(f(n)).$

$($b$)(15$ points$)$ Prove your guess from part $($a$)$ using the substitution method.