0

Why isn't $\log(n!) \leq O(n\log n)$?

I know that $\log(n!)$ is of $\Theta(n\log n)$ but why can't a function that is of $\Theta$ be $\leq$ than a function that is $O$ of the same parameter?

Isn't every function that is $\Theta(n\log n)$ actually lower or equals to $n\log n$ asymptotically (i.e., $O(n\log n)$)?

abiessu
  • 8,115
Georgey
  • 1,589
  • 2
  • 25
  • 39
  • How did this question arise? – abiessu Feb 05 '14 at 15:55
  • @abiessu, while proving lower bound for comparison sorting model in computer science. That's exactly what I mean, a part of the proof says that the equality inequality is the contradiction we need for the proof, but I can't find the contradiction in it. – Georgey Feb 05 '14 at 15:59
  • 1
    Perhaps you could post more detail on what mechanisms are used in the proof so it is easier to answer the question. – abiessu Feb 05 '14 at 15:59
  • 1
    A function of $O(b\log n)$ has the same order as a function of $O(\log n)$, which is strictly less than a function having order $O(n\log n)$. – abiessu Feb 05 '14 at 16:02
  • @abiessu, yes I know that, but my question referred to $O(n\log n)$ and $\Theta(n\log n)$ but someone found it ridiculous and changed $n$ to $b$. – Georgey Feb 05 '14 at 16:06
  • I see, let me think about this for a bit. Remind me of the definition of $\Theta(f(n))$? – abiessu Feb 05 '14 at 16:09
  • @abiessu, I think I know why it isn't true. Is it because there's a function $f \in O(n\log n)$ which holds $f < n\log n$, while there's $g \in \Theta(n\log n)$ which holds $g = n\log n$, is this the reason the inequality fails? – Georgey Feb 05 '14 at 16:09
  • 1
    I don't understand what $f \le O(g)$ means. Can you give a translation with quantifiers ? – mercio Feb 05 '14 at 16:12
  • 2
    yes, I'm a computer scientist by training and I've never seen $\le O(\cdot)$. It's always $f(n)=O(g(n))$ which means you can find some constant $c$ for large enough $n$, $n_0$ such that $f(n)\le cg(n), \forall n\ge n_0$. In this case I don't think there's a contradiction for $\log(n!)=O(n\log n)$ because trivially $\log(n!)=\sum_{i=1}^n \log i \le n\log n$. – TooTone Feb 05 '14 at 16:21
  • @TooTone, this is how my professor proved that the lower bound of comparison sorting algorithms is of $\Omega(n\log n)$, using a proof by contradiction. – Georgey Feb 05 '14 at 16:24
  • @Georgey ok, I think there's a miscommunication somewhere along the line. Maybe you could refer us to the context as other posters have requested? Alternatively, the proof is fairly well known, and you could find one in a text book or online and work through that and then go back to your professor's proof? – TooTone Feb 05 '14 at 16:28
  • @TooTone you're correct, the use of $\leq$ was to illuminate the relation between both function. – Georgey Mar 09 '14 at 13:09

2 Answers2

2

The big-O notation differs from the big-$\Theta$ notation in that $f(n)\in O(g(n))$ means that there is a function in $O(g(n))$ that bounds $f(n)$ from above, while $f(n)\in \Theta(g(n))$ means that there is a function in $\Theta(g(n))$ that bounds $f(n)$ from above and below.

In other words, in order for $\Theta(\log n!)\le O(n\log n)$ we must have constants $k_1,k_2,k_3$ and functions $g_1(n)\in \Theta(\log n!), g_2(n)\in O(n\log n)$ which satisfy $O(g_1(n))\le O(g_2(n))$ and

$$k_1\cdot g_1(n)\le \log n!\le k_2\cdot g_1(n)\\ |n\log n|\le k_3\cdot g_2(n)$$

Since we claimed that $O(g_1(n))\le O(g_2(n))$ (which can also be written $g_1(n)\in O(g_2(n))$ we must also have $k_4$ such that $|g_1(n)|\le k_4\cdot g_2(n)$.

There is no inherent contradiction produced by these claims.

EDIT:

By comparison (bringing in one of the later comments), the big-$\Omega$ notation describes functions that are bounded below by some function. So $f(n)\in \Omega(g(n))$ means there is a function $g_3(n)\in\Omega(g(n))$ and a constant $k_5$ such that

$$k_5\cdot g_3(n)\le f(n)$$

Now a contradiction is possible, but it does not appear that it has been presented yet.

abiessu
  • 8,115
1

It is.

By Stirling's theorem, $\ln(n!) = n\ln n +O(n) =O(n \ln n) $.

marty cohen
  • 107,799