1
$\begingroup$

My textbook states that

any polynomial dominates any logarithm: $n$ dominates $(\log n)^3$. This also means, for example, that $n^2$ dominates $n\log n$

However, it wasn't clear to me what the formal statement was here; what "any logarithm" is seems ambiguous to me- expressions of what form exactly constitute a logarithmic expression? $n \log n$ seems to count as one- they couldn't have simply meant any expression with a logarithm in it to be a logarithmic expression though, as then the statement is clearly false ($n$ doesn't dominate $n \log n$). So what is the precise mathematical meaning of the statement "any polynomial dominates any logarithm" here? If this statement is indeed ambiguous, what is a precise mathematical statement which expresses the sentiment behind this statement- for example, is the statement $(\log x)^k = O(x^k)$ the strongest statement we can make which is encapsulative of the sentiment behind the given expression (in the case of there not corresponding an exact expression to the given statement)?

$\endgroup$
5
  • 1
    $\begingroup$ How about $(\log x )^k = o(x)$ as $x\to\infty$ for any $k$. $\endgroup$
    – messenger
    Commented Jul 8 at 5:33
  • $\begingroup$ That's a squishy statement, but they likely mean any power of logarithms, compositions of logarithms, and combinations thereof. Note that you can't say that this is true for any expression involving logarithms as it fails for something like $\log(x)^{\log(x)}$. These things are mostly heuristics and not meant rigorously. $\endgroup$
    – Cameron Williams
    Commented Jul 8 at 5:40
  • 2
    $\begingroup$ Polynomials are just big bullies. $\endgroup$
    – copper.hat
    Commented Jul 8 at 5:42
  • 1
    $\begingroup$ What does that say about $x^x$? $\endgroup$
    – Cameron Williams
    Commented Jul 8 at 5:44
  • 1
    $\begingroup$ Your book only means $\forall a,b>0\quad (\log n)^a=o(n^b)$, which implies $n^c (\log n)^a=o(n^{b+c})$. $\endgroup$
    – Anne Bauval
    Commented Jul 8 at 6:45

0

Reset to default

You must log in to answer this question.