Solve the recurrence $T(n)=3T(n/3)+\log n$, $T(1)=1$

Question

So $T(n)=3T(n/3)+\log n$ and $T(1)=1$.

I tried to solve this by expanding it out to see a pattern, but I don't really see the pattern:

$T(n/3) = 3T(n/9)+\log (n/3)$

$T(n) = 3[3T(n/9)+\log (n/3)]+\log n$

$T(n) = 9T(n/9)+3\log (n/3)+\log n = 9T(n/9) + log(n^3/9)$

$T(n/9) = 3T(n/27)+\log (n/9)$

$T(n) = 9[3T(n/27)+\log (n/9)] + \log(n^3/9)$

$T(n) = 27T(n/27)+9\log(n/9)+\log(n^3/9) = 27T(n/27)+27\log(n^{12}/729)$: Note that $9\log(n/9)+\log (n^3/9) = \log(n^9/81)+log(n^3/9)=\log(n^{12}/729)$

So we have $T(n)$ following the pattern:

$T(n) = 3T(n/3)+\log n$

$T(n) = 9T(n/9)+\log(n^3/9)$

$T(n) = 27T(n/27)+\log(n^{12}/729)$

...

Or, $T(n)=3^kT(n/3^k)+...$ but I don't know how to express the other parts as functions of $k$.

Afterwards, we can do $n/3^k = 1$ and solve for $k = \log (n)$. Then we can back-substitute $k$ into $T(n)$ and find out what the $\Theta$ notation for $T(n)$ is.

Answer 1

Hint: try $$ T(n) = 3^k T(n/3^k) + A_k\log n - \log B_k $$and find a recursive relation for $A_k,B_k$.

---

You have $A_1 = 1, B_1 = 1$.

If $$T(n) = 3^k T(n/3^k) + A_k\log n - \log B_k$$ then $$T(n) = 3^k \left[3T(n/3^{k+1})+\log \frac n{3^k}\right] + A_k\log n - \log B_k \\ = 3^{k+1} T(n/3^{k+1}) + 3^k\log n + A_k\log n - \log B_k - 3^k\log 3^k $$ so you have the correct representation with $$ B_{k+1} = 3^{k3^k} B_k \\ A_{k+1} = A_k + 3^k $$

Answer 2

There is a universal way to solve this kind of recurrences - it's called Master Theorem.