Recurrence of T(n) = T(n/3) + T(2n/3)
Hint: Suppose that $T(m) \leq Cm$ for all $m &lt; n$, and that $n$ is divisible by $3$. Then
$$ T(n) = T(n/3) + T(2n/3) \leq C(n/3) + C(2n/3) = Cn. $$
Use this to obtain a good bound on $T(n)$ when $n$ is a power of $3$.