0

In order to prove that $n$ is $O(n\log n)$, as per my understanding if we have to say $f(n)$ is $O(g(n))$ then $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)}= C$

Then in that case when I am taking the limit $\lim\limits_{n\to\infty} \frac{n}{n\log n}= \frac{1}{1+\log n}$

This is not a constant but when I do trial and error I am getting $C$ and $n_0$ as $1$ and $2$

Where exactly I am doing wrong can someone please help me

Regards, Siddartha

Michael Hardy
  • 1
Siddarth
  • 133
  • 3
    Please revise your understanding of $O$, the one in your question is wrong. – Did Aug 13 '16 at 08:59
  • Is my definition of $O$ is wrong? i.e. $f(n)$ is $O(g(n))$ if and only if $\lim\limits_{n \to \infty} \frac{f(n)}{g(n)}<= C$ isnt this right? kindly help me where I am going wrong? – Siddarth Aug 14 '16 at 07:50
  • Indeed, wrong definition (both the version in the post and the modified version in your comment) since the limit may not exist. Why not check some reference? – Did Aug 14 '16 at 08:21

4 Answers4

2

$f(n) \in O(g(n))$ provided that there exist $M>0, x \in \Bbb{R}$ such that whenever $m>x$ we have $|f(m)| < M|g(m)|$. In other words, $|f|$ is eventually bounded above by some constant multiple of $|g|$. For example, if $f(n)=n$ and $g(n) = n\log(n)$, we can let $M = 1$ and $x = 2$; then we have that whenever $n > 2$, $n \leq n\log(n)$, and so $n\in O(n\log(n))$.

(assuming $\log$ is base $2$)

florence
  • 12,819
1

It is not true that if $f$ is $O(g)$ then $\lim_{n\to\infty} \frac{f(n)}{g(n)} = C$ for some $C$. Consider for example the function $\sin$ which is in $O(1)$, simply because for all $n$ we have $\sin(n)\leq 1$, yet the limit $\lim_{n\to\infty} \frac{sin(n)}{1}$ fails to exist.

Now, in your case the limit does exist: we have $\lim \frac{n}{n\log n} = \lim \frac1{\log n} = 0$, and therefore $n\in O(n\log n)$.

zarathustra
  • 4,891
0

Taking the limit,

$$\lim_{n \to \infty} \frac{n}{n\log(n)} = \lim_{n \to \infty} \frac{1}{\log(n)}= 0$$ which is a constant, thus $n$ is $\mathcal{O}(n\log(n))$.

EDIT: If you want to use the more traditional definition (i.e. finding a $c$ and $x_0$ such that for all $x \geq x_0$, $x \leq c \cdot x\log(x)$.) If we pick $c=1$ and $x_0 = 10$, then for all $x \geq x_0 = 10$, we have $\log(x) \geq \log(10) = 1$, thus, $$x = x \cdot 1 \leq x \cdot \log(x) = 1\cdot x\log(x) = c\cdot x\log(x).$$

Thus, we have found a $x_0$ and $c$ that satisfies the definition, so $n$ is $\mathcal{O}(n\log(n))$.

benguin
  • 3,846
0

you have the wrong operator here. it can not be = as $f(x)=O(g(x))$ says "$f$ does not grow faster than $g$". So you might not be able to find a constant. The right definition is

$$\limsup_n \frac{f(n)}{g(n)} < \infty$$

Michael Hardy
  • 1
Ulfgard
  • 221