Simplifying Equation - Asymptotic analysis

Question

The textbook I'm using for the course Introduction to Algorithms class has the following statement in it:

The equation of such a line is

$\log (T(N)) = 3 \log N + \log a$

(where a is a constant) which is equivalent to

$T(N) = a N^{3}$

My rusty algebra just cannot get me from the first one to the second one. My last math class, a graduate level intro to stats class, was twenty years ago.

Can someone walk me through how they got from the first equation to the second equation?

Answer 1

You just have to remember, that \begin{align} \log(a)+\log(b) = \log(a\cdot b) \end{align} And secondly \begin{align} c\cdot\log(a)=\log(a^c) \end{align} From that follows that \begin{align} 3\log(N)+\log(a) = \log(N^3)+\log(a) = \log(aN^3)= \log(T(n)) \end{align} So $T(n) = aN^3$.

Note: This holds for $\log, \quad\log_{10}, \quad \log_x$ or whatever you take as your basis.