0
$\begingroup$

I'm trying to understand a "subproof" of the divisor Master Theorem (Cormen et al., Introduction to Algorithms, page 99), and in some point they state:

$$\Large a^{\log_b n} = n^{\log_b a}$$

where $a\geq 1$, $b > 1$ and $n = b^i$, for some $i$. That is, $n \in \{1, b, b^2, ...\}$

I would appreciate a simple explanation of this equality (just OK for a CS undergraduate).

$\endgroup$
  • 5
    $\begingroup$ Take the log (to the base $b$) of both sides. $\endgroup$ – André Nicolas Aug 2 '16 at 21:48
  • 1
    $\begingroup$ Alternatively, write out both sides using the rule that $s^t = e^{t \ln s}$, and recall that $\log_a x = \frac{\ln x}{\ln a}$. $\endgroup$ – John Hughes Aug 2 '16 at 21:51
  • $\begingroup$ Black Bolt is capable of channeling all available energy into one devastating punch called his Master Blow, which renders him extremely vulnerable subsequently. $\endgroup$ – Will Jagy Aug 2 '16 at 21:53
  • $\begingroup$ @WillJagy I -really- wonder what's the relation between logarithms and Marvel... $\endgroup$ – JnxF Aug 2 '16 at 22:06
  • $\begingroup$ @WillJagy are you proposing we use the Master Blow to prove the Master Theorem? I feel like this is the best approach I've ever heard. Only problem is that it might leave a major singularity where the blow occurred, but it should be removable XD $\endgroup$ – Brevan Ellefsen Aug 2 '16 at 22:30
2
$\begingroup$

Let us start here:

$$\log_b(a)\log_b(n)=\log_b(n)\log_b(a)$$

$$b^{\left(\log_b(a)\log_b(n)=\log_b(n)\log_b(a)\right)}$$

$$b^{\log_b(a)\log_b(n)}=b^{\log_b(n)\log_b(a)}$$

$$\left(b^{\log_b(a)}\right)^{\log_b(n)}=\left(b^{\log_b(n)}\right)^{\log_b(a)}$$

Recall that $x^{\log_x(y)}=y$, so

$$a^{\log_b(n)}=n^{\log_b(a)}$$

$\endgroup$
1
$\begingroup$

For this particular nut, since $n =b^i$ your equality is just $$a^{\displaystyle \log_b b^i} = a^{\displaystyle i} = b^{\displaystyle \log_b a^i}$$

and so it holds. It's also true for a more general $n$, as the comments explain.

$\endgroup$
0
$\begingroup$

It's true for all $a,b,n>0$

\begin{align*} \large \frac{\log a}{\log b} \times \log n &= \large \frac{\log n}{\log b} \times \log a \\[5pt] \large \log_{b} a \times \log n &= \large \log_{b} n \times \log a \\[5pt] \large \log \left( n^{\log_{b} a} \right) &= \large \log \left( a^{\log_{b} n} \right) \\[5pt] \large n^{\log_{b} a} &= \large a^{\log_{b} n} \end{align*}

$\endgroup$

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.