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.

  • 1
    $\begingroup$ 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) $\endgroup$ – 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}\ .$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.