0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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 $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ in one of my lectures i have solved this problem $\endgroup$ – Dr. Sonnhard Graubner Oct 22 '14 at 22:07
  • $\begingroup$ which one?${{}}$ $\endgroup$ – mookid Oct 22 '14 at 22:09
  • $\begingroup$ your equation above $\endgroup$ – Dr. Sonnhard Graubner Oct 22 '14 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.