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