Saturday, 21 April 2018

functions - Which one grows asymptotically faster g(n)=1079nlogn or f(n)=3logn?




I'm trying to understand which of the following functions



g(n)=1079nlogn



and



f(n)=3logn



grows asymptotically faster.




I know f(n)=nlogn. I tried to compare the log of both functions above, that is



logg(n)=log1079nlogn=log1079+logn+log(logn)



and



logf(n)=log3logn=log3logn



Asymptotically, logn dominates log(logn) and log1079 becomes irrelevant. log3 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) faster?


Answer



Using base 10 logs as specified in a comment



3log10n=3log103log3n=nlog103<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 limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...