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

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.

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$$
• which one?${{}}$ – mookid Oct 22 '14 at 22:09