0

If I have the function

$$f(n)=n \log_{10}n$$

Is it correct to say that the asymptotic bound, in little-o notation, for $f(n)$ is $o(n \log_2n)$? $~\forall~n>0$, $n \log_2n$ would strictly be an upper bound for $n \log_{10}n$, but does this meet the definition of little-0 because they would be equal when $n=0$?

Jaideep Khare
  • 19,293
tpm900
  • 139
  • 3
    It's not little-$o$. Use: $\log_{a} b \log_b {c} = \log_a c$. – Thomas Andrews Apr 11 '17 at 17:54
  • 1
    It's useful to know that logs of different bases with the same argument only differ by a constant factor. This is part of why we usually only use one base (generally either $2$, $e$, or $10$) in any given context. – Ian Apr 11 '17 at 17:55
  • 3
    (You seem to be confused about what liitle-$o$ means, however. It does not mean being an upper bound. It might be worth reviewing the definition of little-$o$.) – Thomas Andrews Apr 11 '17 at 17:56

1 Answers1

0

No, it is not. $f(n)$ is asymptotically (up to constants) behaving like $n\log_2 n$, i.e. $f(n) = \Theta(n\log_2 n)$ (actually, a slightly stronger statement holds here, but that's not important).

Equivalently, by definition of the $\Theta(\cdot)$ notation, you have both (i) $f(n) = O(n\log_2 n)$ and (ii) $f(n) = \Omega(n\log_2 n)$.

However, you do not have $f(n) = o(n\log_2 n)$, which would essentially mean $\frac{f(n)}{n\log_2 n}\xrightarrow[n\to\infty]{} 0$ (and is incompatible with (ii)): i.e., that would mean "$f(n)$ is negligible in front of $n\log_2 n$." Maybe you are confusing $O(\cdot)$ and $o(\cdot)$?

Clement C.
  • 67,323