Since this question is asked frequently I will try to work out a
solution for generic positive integers $a$ where $a\ge 2$.
Suppose we have $T(0)=0$ and
$$T(1)=T(2)=\ldots =T(a-1)=1$$
and for $n\ge a$
$$T(n) = a T(\lfloor n/a \rfloor) + n \lfloor \log_a n \rfloor.$$
Furthermore let the base $a$ representation of $n$ be
$$n = \sum_{k=0}^{\lfloor \log_a n \rfloor} d_k a^k.$$
Then we can unroll the recurrence to obtain the following exact
formula for $n\ge a$
$$T(n) = a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1}
a^j \times (\lfloor \log_a n \rfloor - j) \times
\sum_{k=j}^{\lfloor \log_a n \rfloor} d_k a^{k-j}.$$
Now to get an upper bound consider a string consisting of the digit
$a-1$ to obtain
$$T(n) \le a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1}
a^j \times (\lfloor \log_a n \rfloor - j) \times
\sum_{k=j}^{\lfloor \log_a n \rfloor} (a-1) \times a^{k-j}.$$
This simplifies to
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1}
a^j \times (\lfloor \log_a n \rfloor - j) \times (a-1)
\sum_{k=0}^{\lfloor \log_a n \rfloor-j} a^k$$
which is
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1}
a^j \times (\lfloor \log_a n \rfloor - j)
(a^{\lfloor \log_a n \rfloor + 1 -j} -1)$$
which turns into
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1}
(\lfloor \log_a n \rfloor - j)
(a^{\lfloor \log_a n \rfloor + 1} - a^j).$$
The sum produces four terms.
The first is
$$\lfloor \log_a n \rfloor^2
a^{\lfloor \log_a n \rfloor + 1}.$$
The second is
$$- \lfloor \log_a n \rfloor
\frac{a^{\lfloor \log_a n \rfloor}-1}{a-1}.$$
The third is
$$- \frac{1}{2} a^{\lfloor \log_a n \rfloor + 1}
(\lfloor \log_a n \rfloor -1) \lfloor \log_a n \rfloor$$
and the fourth is
$$\frac{1}{(a-1)^2}
\left(a + a^{\lfloor \log_a n \rfloor}
(\lfloor \log_a n \rfloor (a-1) -a)\right).$$
This bound represented by these four terms plus the leading term is
actually attained and cannot be improved upon. For the asymptotics we
only need the dominant term, which is
$$\left(a - \frac{1}{2} a \right)
\lfloor \log_a n \rfloor^2
a^{\lfloor \log_a n \rfloor}
= \frac{1}{2} a \lfloor \log_a n \rfloor^2
a^{\lfloor \log_a n \rfloor}.$$
Now for the lower bound, which occurs with a one digit followed by
zeroes to give
$$T(n) \ge a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1}
a^j \times (\lfloor \log_a n \rfloor - j) \times
a^{\lfloor \log_a n \rfloor-j}.$$
This simplifies to
$$a^{\lfloor \log_a n \rfloor}
+ \sum_{j=0}^{\lfloor \log_a n \rfloor -1}
(\lfloor \log_a n \rfloor - j) \times
a^{\lfloor \log_a n \rfloor}$$
which is
$$a^{\lfloor \log_a n \rfloor}
+ a^{\lfloor \log_a n \rfloor}
\sum_{j=0}^{\lfloor \log_a n \rfloor -1}
(\lfloor \log_a n \rfloor - j)$$
which finally produces
$$a^{\lfloor \log_a n \rfloor}
+ a^{\lfloor \log_a n \rfloor}
\sum_{j=1}^{\lfloor \log_a n \rfloor} j$$
or
$$a^{\lfloor \log_a n \rfloor}
+ \frac{1}{2}
\lfloor \log_a n \rfloor (\lfloor \log_a n \rfloor +1)
a^{\lfloor \log_a n \rfloor}.$$
The dominant term here is
$$\frac{1}{2}
\lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor}.$$
Joining the dominant terms of the upper and the lower bound we obtain
the asymptotics
$$\color{#00A}{\lfloor \log_a n \rfloor^2 \times
a^{\lfloor \log_a n \rfloor}
\in \Theta\left((\log_a n)^2 \times a^{\log_a n}\right)
= \Theta\left((\log n)^2 \times n\right)}.$$
This MSE link has a series of similar calculations.
Starting where you left off:
$S(m)=S(m/2)+ \Theta(\lg m)$
Compared this to the generic recurrence:
$T(n) = aT(n/b) + f(n)$
Let's address the questions, you raised.
What does "polynomially" larger mean?
A function $f(n)$ is polynomially larger than another function $g(n)$, if $f(n) = n^i g(n)/t(n)$, where $t(n)$ is some sub-polynomial factor such as $\log n$, etc that appears in $g(n)$. In other words, we want to see, ignoring sub-polynomial and constant factors, if $f(n)$ is a polynomial multiple of $g(n)$.
Does case 2 apply here?
Recall that Case 2 of the master theorem applies when $f(n)$ is roughly proportional to $n^{\log_b a}\log^kn$ for some $k \ge 0$. Now, applying all this to your equation above, $a = 1$, $b=2$ and $f(m) = \Theta(\log m)$. This give $k = 1$ and since $m^{\log_2 2^0}\log^km = \Theta(\log m)$, case 2 does apply.
What is the solution using Case 2?
Generally, when case 2 does apply, the solution is always of the form $\Theta(n^{\log_b a}\log^{k+1}n)$. So, in your case, it'll be $\Theta(\log^2 m)$ as you've already figured.
Best Answer
I assume by $f(n)$, you mean your recurrence relation to be of the form $$ T(n)=aT\left(\frac{n}{b}\right)+f(n), $$ so that in this case you have $a=3$, $b=2$, and $f(n)=0$ for all $n$.
That being the case: yes, $f(n)=0$ is perfectly acceptable.
To answer your more specific questions:
Yes, $0=O(n^{\log_2(3)})$. Take absolutely any $n_0\in\mathbb{N}$ and any $c>0$, and it is true that $0\leq cn^{\log_2(3)}$ for all $n\geq n_0$. Remember, Big-O just represents asymptotic upper bounds; of course something that goes to infinity is an upper bound, in the limit, for $0$.
Yes, $0$ is 'asymptotically smaller' than $n^{\log_2(3)}$. Take absolutely any $\epsilon\in(0, \log_2(3))$, and it is true that $0=O(n^{\epsilon})$.
The Master Theorem is perfectly applicable in this situation, and it shows that your $T(n)$ satisfies $T(n)=\Theta(n^{\log_2(3)})$.