Master theorem, algorithms $T(n) = 2T(n/3) + \log n$

Question

Can I solve
$ T(n) = 2T(n/3) + \log n $ using the master theorem?
It doesn't seem to fit in any case.

Answer 1

Perhaps this doesn't use the master theorem, but your problem screams for a logarithm. I plugged in $T(n)=a\log n+b$ and got $a=-1$ and $b=-2\log 3$. Natural logarithms, of course.

Answer 2

We can give a solution to the following recurrence $$T(n) = 2 T(\lfloor n/3 \rfloor) + \lfloor \log_3 n \rfloor$$ for $n\ge 3$ where we set $T(1) = T(2) = 1.$

Now it is not difficult to see that for $n\ge 3$ we have the exact relation $$T(n) = 2^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 2^j (\lfloor \log_3 n \rfloor - j )$$ which is independent of the ternary digits of $n.$

This simplifies to $$3\times 2^{\lfloor \log_3 n \rfloor} - \lfloor \log_3 n \rfloor - 2.$$ The dominant term here is clearly $2^{\lfloor \log_3 n \rfloor}$ so that

$$T(n)\in \Theta\left(2^{\lfloor \log_3 n \rfloor}\right) = \Theta(3^{\log_3 2 \times \log_3 n}) = \Theta(n^{\log_3 2}).$$

The Master theorem does apply here. This MSE link presents several related computations.