Which one grows asymptotically faster $g(n) = 10^{120} n \sqrt{n}$ or $f(n) = 3^{\log n}$?

304 Views Asked by At

I'm trying to understand which of the following functions

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

$$g(n) = 10^{120} n \sqrt n$$

asymptotically (i.e. as $n \to \infty$) grows faster, but I'm not really sure how to approach this problem.

I tried to compare the logarithms of both functions, that is $$\log f = \log 3^{\log n} = \log n \log 3$$ and $$\log g = \log (10^{120} n \sqrt n) = \log 10^{120} + \frac{3}{2} \log n$$

Ignoring the constant addend $\log 10^{120}$, what this tells me is that depending on the logarithm of the functions above that I use, either $f$ or $g$ dominates one over the other.

Any more cleverer way to solve this?

2

There are 2 best solutions below

5
On BEST ANSWER

Hint. Here you can ignore the multiplicative constant $10^{120}$. Note that $$3^{\log_b n}=b^{\log_b 3\cdot \log_b n}=n^{\log_b 3},\quad n\sqrt{n}=n^{3/2}$$ Now compare the exponents $\log_b 3$ with $3/2$.

0
On

Using a chain of continuous and monotonous substitutions:

$3^{\log(n)} = 3^m = 3^{2o}= (3^2)^o \lt (e^3)^o = e^{3o} = e^{1.5m} = e^m * e^\sqrt{m} =n \sqrt{n} < 10^{120} n \sqrt{n} $ for sufficiently large $n$

with: $e^m = \log(n) $ and $m = 2o$