For example:
$F(n) = \log(n) + 3\log^5(n^2) + 2\log^3(n)$
What would the asymptotic notation be since the logarithms have a different exponent. Are higher exponent logs more dominant in the notation?
Asked
Active
Viewed 189 times
0
-
Yes, $\ln^5(n^2)/\ln(n)=2^5\ln^4(n)\to\infty$. It is not common, but do check in the context in case that they are denoting by $\ln^5(n^2)$ the function $(\ln(n^2))^5$ and not the composition of $\ln$ five times onto $n^2$. If that were the case then, it would be the other way around. – user647486 Mar 19 '19 at 00:28
-
so would $log^5(n)$ be more dominant than $log(n)$? Also, how do the exponent within the log function affect the outcome? – Code4life Mar 19 '19 at 00:40
-
Yes, if the quotient tends to infinity, then the numerator is diverging faster. The exponent inside goes out as a multiplicative constant. – user647486 Mar 19 '19 at 00:41
2 Answers
0
Classify by degree:
$F(n)\sim_\infty 96\log^5(n)$.
Bernard
- 175,478
-
-
@ClaudeLeibovici: because $3\log^5(n^2)=3(2\log n)^5$=3\cdot2^5\log^5n$. – Bernard Mar 19 '19 at 10:04
-
I just feel stupid ! I leave my comment on purpose. Cheers :-( – Claude Leibovici Mar 19 '19 at 10:05
-
It happens to all of us to be adsent-minded – I could myself be in the Guinness World Records ;o) – Bernard Mar 19 '19 at 10:11
0
Make $x=\log(n)$ to get $$F(x)=6 x^5+2 x^3+x=6x^5\left(1+\frac 1{3x^2} +\frac 1{x^4}\right)\sim 6 x^5$$
Claude Leibovici
- 260,315