2
$\begingroup$

I have some questions about the examples I came by in a book that helps me to explore the world of programming.

I understand what Big-O notation is and interested in the following:

1. To prove if $g(n) \in O(f)$, everything we need is to find only one set of ($c$ and $n_0$) that $g(n) \leq c\cdot f(n)$ , $n>n_0$. So, for example, if I found 1 set that holds this inequality and 10 that don't, $g(n) \in (O(f))$ anyway. Other words, it's sufficient to find only ONE set of($c$,$n_0$) that holds the inequality to prove it or not?

2. To disprove it, we need to find $N$ that after $c$ and $n_0$ have been chosen doesn't hold the inequality. If I can't do it with the chosen set of $c$ and $n_0$ does it mean that I can't disprove it?

Here is the example I am perplexed about:

We know that $n$ is in $O(n^2)$ but $(n^2)$ is not in $O(n)$.

To prove the first statement we have to prove that $n \leq c\cdot n^2$ and it's clear enough that doesn't need any explanation.

But if we reverse it and try to prove that $n^2$ is in $O(n)$, which is obviously not true, there is some mystery that I can't find an answer to. We pick $c=n$ and the inequality becomes $n^2 \leq n\cdot n$, so they become equal and from that is seems that $n^2$ is IN $O(n)$, because we can't find any values of n that the inequation doesn't hold.

Thanks in advance and sorry if the question is very stupid.

$\endgroup$
2
$\begingroup$

The question is not stupid and arises from an understandable point of view. The key point is that $c$ must be a constant. On the other hand, $n$ is the parameter that is tending towards $\infty$. Thus you cannot pick $c = n$ because $n$ keeps increasing.

Everything else you said is right. To prove it is in $O(f)$ it suffices to find one set of ($c$, $n_0$). To disprove, you must show that regardless of ($c$, $n_0$), the function grows too fast.

$\endgroup$
  • 1
    $\begingroup$ Thx, the solution just came up to my mind today, but I wasn't sure whether it's correct or not. The book that I read has as an example where c=n and they consider it as n^2, but it's just an example that proves the thing the author wanted to prove and doesn't play a part in my question. Thx! $\endgroup$ – Dmitrii Jan 12 '17 at 16:10
  • $\begingroup$ @Dmitrii you are most welcome $\endgroup$ – RGS Jan 12 '17 at 16:18
1
$\begingroup$

Your argument for $n = O(n^2)$ is correct.

For $n^2 \ne O(n)$, you can't pick $c=n$; because $c$ must be a constant.

Suppose you pick the constant $c=17$. Then you would need to also pick $n_0$ so that $n^2 < 17n$ for all $n>n_0$. But you can't do this because there is no such $n_0$: whenever $n$ is at least $17$, then $n^2 < 17n$ is false. Okay, $c=17$ didn't work, perhaps $c=1019$ will work instead. Then you would need to pick $n_0$ so that $n^2 < 1019n$ for all $n>n_0$. This is also impossible.

$\endgroup$
  • $\begingroup$ Yea, thx a lot! $\endgroup$ – Dmitrii Jan 12 '17 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.