Solve $T(n)=2T(\frac{n}3)+\log_3(n)$ for n>1, n a power of 3

Question

Solve the following recurrence equation using the characteristic equation.

$T(n)=2T(\frac{n}3)+\log_{3}n$ for $n>1$, $n$ a power of $3$

$T(1)=1$

I'm not quite sure I understand exactly what to do here. I've done this much on my own

Let $n=3^k$, $k=\log_{3}n$ $T(3^k)=2T(\frac{3^k}{3})+k$

$T(3^k)=2T(3^{k-1})+k$

Let $t_{k}=T(3^k)$

$t_{k}=2t_{k-1}+k$

But that's as far as I can get. After that, I'm completely lost. Even when I'm trying to follow the example in the book, it seems like either a lot of intermediate steps are skipped or the example doesn't fit my question. Any assistance would be appreciated.

Answer 1

You have $t_k - 2t_{k-1} = k$ with the condition $t_0 = 1$ (why?)

The characteristic equation would have been $x-2 = 0$ if the equation was homogeneous (i.e. RHS was $0$). This would have given us the solution $t_k = a 2^k$. However given that there is a linear function in the RHS, we should explore solutions of form $t_k = a 2^k + (bk + c)$.

Substitute in the recurrence and see if we can find values for $b, c$ s.t. the recurrence holds for all $k$. Then use the initial condition to find $a$...

Answer 2

Look carefully and I think you can see that $t_{n+1}$ = $t_n + 3$. Now run that observation back to T(1) = 1 $\Rightarrow t_1 = 1$. At this point you should be able to write $t_n$ just in terms of n and without any other t's.

Answer 3

We can actually solve this recurrence exactly and not just for powers of three, at any rate one that is very close. Consider $$T(n) = 2 \; T(\lfloor n/3\rfloor) + \lfloor\log_3 n\rfloor+1$$ with $T(0) = 0$ and which has $T(1) = 1.$ The constant one has lower order than the logarithm so the complexity is the same as in the original query. (Note $|\lfloor\log_3 n\rfloor-\log_3 n | < 1$ and that $|\lfloor\log_3 n\rfloor+1-\log_3 n | < 1$ so adding in one introduces the same error as using the floor alone.)

The key observation is that the answer does not depend on $n$ but only on the number of digits in base three that it has, i.e. the logarithm.

If $$n= \sum_{k=0}^{\lfloor\log_3 n\rfloor} d_k 3^k \quad\text{then}\quad T(n) = \sum_{k=0}^{\lfloor\log_3 n\rfloor} 2^k \; (\lfloor\log_3 n\rfloor+1-k) = 4 \times 2^{\lfloor\log_3 n\rfloor} -\lfloor\log_3 n\rfloor -3.$$

This formula is exact for all $n.$ Now clearly the dominant term is the exponential one which gives the following complexity: $$\Theta\left(2^{\lfloor\log_3 n\rfloor}\right) = \Theta\left(3^{\log_3 2 \times \lfloor\log_3 n\rfloor}\right) = \Theta(n^{\log_3 2}).$$

This is of course the same as what the Master theorem would produce. Here is another calculation of the same type that is a bit more advanced.