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=log3∗logn
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=3log103⋅log3n=nlog103<n
Note how this would change if the base for the log were e or 2
No comments:
Post a Comment