How to solve recurrence $T(n) \le 2T(n/3) + c\log_3 n$ using substitution method
Here is what happens when you use the substitution method, assuming a base case of $T(1) = 0$ and $c=1$:
\begin{align}
T(3^m) &amp;\leq m + 2T(3^{m-1}) \\ &amp;\leq
m + 2(m-1) + 2^2T(3^{m-2}) \\ &amp;\leq
m + 2(m-1) + 2^2(m-2) + 2^3T(3^{m-3}) \\ &amp;\leq \ldots \\ &amp;\leq
m + 2(m-1) + 2^2(m-2) + \cdots + 2^{m-1}(1) + 2^m T(1) \\ &amp;=
m + 2(m-1) + 2^2(m-2) + \cdots + 2^{m-1}(1) \\ &amp;=
m(1 + 2 + \cdots + 2^{m-1}) - (2 + 2^2 + \cdots + 2^{m-1}) - (2^2 + \cdots + 2^{m-1}) - \cdots - (2^{m-1}) \\ &amp;=
m(2^m-1) - (2^m-2) - (2^m-2^2) - \cdots - (2^m-2^{m-1}) \\ &amp;=
m(2^m-1) - (m-1)2^m + (2 + 2^2 + \cdots + 2^{m-1}) \\ &amp;=
m(2^m-1) - (m-1)2^m + (2^m-2) \\ &amp;=
2^{m+1}-m-2.
\end{align}
This shows that $T(n) = O(n^{\log_32})$.