Saturday, 21 April 2018

functions - Which one grows asymptotically faster $g(n) = 10^{79} n log n$ or $f(n) = 3^{log n}$?




I'm trying to understand which of the following functions



$$g(n) = 10^{79} n \log n$$



and



$$f(n) = 3^{\log n}$$



grows asymptotically faster.




I know $f(n) = n^{\log n}$. I tried to compare the log of both functions above, that is



$$\log g(n) = \log {10^{79} n \log n} = \log {10^{79}} + \log n + \log (\log n)$$



and



$$\log f(n) = \log {3^{\log n}} = \log 3 * \log n$$



Asymptotically, $\log n$ dominates $\log (\log n)$ and $\log {10^{79}}$ becomes irrelevant. $\log 3$ is also a constant and asymptotically does not matter, but it's a multiplicative constant, so I'm tempted to say that $f$ actually grows faster asymptotically. Am I correct? If I am correct, does this hold for every base of logarithms?




Any other cleverer way to show which function grows asymptotically (i.e. as $n \to \infty$) faster?


Answer



Using base $10$ logs as specified in a comment



$3^{\log_{10} n}=3^{\log_{10}3 \cdot \log_3 n}=n^{\log_{10}3}\lt n$



Note how this would change if the base for the log were $e$ or $2$


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...