How does my professor go from this logarithm to the next?

Question

In the above picture, how does he go from the third-last line to the second last?

Answer 1

The answer is obvious following the comments by yourself (the logarithm is to base 3) and by Mufasa and Daniel:

$ \phantom{==} 3 \, c \, (n/3) \log_3 (n / 3) + n \\ = c \, n \log_3 ( n / 3 ) + n \\ = c \, n \, \left( (\log_3 n) - (\log_3 3) \right) + n \\ = c \, n \, \left((\log_3 n) - 1\right) + n $

because $log_3 3 = 1$.

Sorry for not stating this in a comment (I do not yet have enough reputation points to add a comment to a question).

Answer 2

Your professor is using lazy but fairly widespread notation between the third-last and second-last lines, where he just uses $c$ to mean some arbitrary constant that doesn't depend on $n$ - you'll note that a factor of $1/3$ also goes missing there, as well as the base of the logarithm magically being set equal to $3$. What's more likely is that the value of $c$ actually changes through the argument.

To be more specific, as you may already know, for any sane choices of $a, x$ and $y$:

$$ \log_x(a) = \frac{\log_y(a)}{\log_y(x)} $$

So, to expand on the argument, we can show that $T(n) \leqslant c n \log_b n$ for large $n$, arbitrary $b$ and constant $c$ similarly to before:

\begin{align*} T(n) &\leqslant 3c\left(\frac{n}{3}\right) \log_b\left(\frac{n}{3}\right) + n \qquad \mbox{for some constant $c$} \\ &= 3c\left(\frac{n}{3}\right)\frac{\log_3(n/3)}{\log_3(b)} \\ &= 3c'n(\log_3(n) - 1) \qquad \mbox{for some other constant $c'$} \end{align*}

I suspect that your professor is trying to show that $T(n) \in O(n \log n)$. For this, it suffices to show that for any $n \geqslant n_0$, $T(n) \leqslant cn \log n$, for some fixed constants $c$ and $n_0$. Specifically, $c$ should not depend on $n$, but besides that we don't need to care what it is, so it's not worth rigorously keeping track of its value. Rather than writing $c, c', c'', c''', ...$ through the argument, we just write $c$.

If you're doing algorithm analysis, the base of the logarithm isn't usually relevant - if $T(n) \leqslant c n \log_b n$ holds for a specific $b$ and constant $c$, it holds for any $b$ with some other constant $c$.