# Log property in proof of Master theorem

The family of recurrence considered is of the form

$$T(n) = aT(n/b) + n^c$$ $a,b,c$ are integers.

One case of master theorem states:

if $c< log_b a$, then $T(n) = \Theta(n^{log_b a})$. I have a doubt in a specific line of the proof for this case, which requires a specific log-property.

\begin{align} n^c \left(\frac{a}{b^c}\right)^{log_b n} & = n^c \frac{a^{log_b n}}{(b^c)^{log_b n}} \\ & = n^c \frac{n^{log_b a}}{n^{log_b b^c}} \\ & = n^c \frac{n^log_b a}{n^c} \\ & = n^{log_b a} \end{align}

My problem is in step 2, where $a^{log_b n}$ becomes $n^{log_b a}$.

When I tried out the proof, the final answer I ended up with was $a^{log_b n}$

What property of logarithms, am I missing out here. Thanks in advance.

• Let a and b be two positive real numbers:$a^{\ln(b)} = (e^{\ln(a)})^{\ln(b)} = e^{\ln(a)*\ln(b)} = (e^{\ln(b)})^{\ln(a)} = b^{\ln(a)}$. What I wrote stays true with regards to any integer basis of logarithms, which is your case (base b) – mvggz Nov 27 '14 at 11:48

Using the rule for logarithm of a power, $$\log_b(a^{\log_bn})=(\log_bn)(\log_ba)=(\log_ba)(\log_bn)=\log_b(n^{\log_ba})\ .$$ So $$a^{\log_bn}=n^{\log_ba}\ .$$