1

I am reading about master theorem and it says that the number of leaves is $a^{\log _{b} n}$, and this part I can understand.

But then it immediately concludes that $$ a^{\log _{b} n} = n^{\log _{b} a} $$ which I am not getting. I verified that it is true by plugging in some values and also I tried to prove it by looking up properties of logatirthms but that didn't seem to help.

Can someone provide an explanation to why this is true?

Fazzolini
  • 1,223
  • 5
    Just take $\log_b$ of both sides. – lulu Jul 15 '21 at 23:08
  • 2
    Take $\log_b$ of both expressions. – saulspatz Jul 15 '21 at 23:09
  • So what I'm hearing, @lulu and saulspatz, is that you should take $\log_b$ of both sides, am I getting that right? :-) ¶ OK, just so this isn't just snark (however compassionate), let me point out that one way that it might occur to a student to do such a thing is that (a) there are logs aplenty here, and (b) if you take the log of $p^q$, then you get $q \log p$, so it's an easy way to kind of "homogenize" the expression by getting everything in terms of logs. It's definitely something that comes with experience. – Brian Tung Jul 16 '21 at 02:11

2 Answers2

4

Take $\log_b$ of both: $$\log_b(a^{\log_bn})=\log_b(n)\log_b(a)$$ $$\log_b(n^{\log_ba})=\log_b(a)\log_b(n)$$

Henry Lee
  • 12,215
4

Are you familiar with the following: for any $c,d>1$: $d = c^{\log_c d}$. This follows from the definition of logarithm. I trust you also know the equation $e^{fg} = (e^f)^g$, for all positive $e,f,g$.

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

The first and last "$=$" following from the fact that $d = c^{\log_c d}$ for any $c,d>1$, and the remaining "$=$" following from the fact that the equation $e^{fg} = (e^f)^g$ holds for all positive $e,f,g$.

Mike
  • 20,434