4

Please, can someone here help me to understand the Big-O notation in discrete mathematics?

Determine whether $F(x)= 5x+10$ is $O(x^2)$

Zev Chonoles
  • 129,973
user83632
  • 51
  • 1
    http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o This thread contains some of the best explanations for a beginner. – vaidy_mit Jun 24 '13 at 03:01
  • can you answer this pertaining to my problem – user83632 Jun 24 '13 at 03:02
  • I guess it is not,because you see 5x+10 is linear.So the function of x increases in a linear way corresponding to x.Hence it is O(x). – vaidy_mit Jun 24 '13 at 03:06
  • 4
    @vaidy_mit Actually, that's not true. Big-O gives only an upper bound - so, being $O(x)$ automatically makes you $O(x^2)$ as well (given that $x\rightarrow\infty$). What you describe is actually $\Theta$- (that is, Big-Theta) notation. – Nick Peterson Jun 24 '13 at 03:08
  • @ nrpeterson Thanks sir !! @ user83632 sorry for directing you in a wrong way !! And yeah,big O can be otherwise called as worst case complexity,and hence it can be O(x2) . – vaidy_mit Jun 24 '13 at 03:13

4 Answers4

8

Let us give a definition for Big-O notation:

Suppose $g(x)\geq 0$. We say that $f(x)=O(g(x))$ as $x\rightarrow\infty$ if:

Loosely: $\lvert f(x)\rvert$ is bounded by a constant multiple of $g(x)$ for $x$ sufficiently large.

Rigorously: There exists $C>0$ and $X\in \mathbb{R}$ such that for all $x>X$, we have $\lvert f(x)\rvert \leq Cg(x)$.

In your case, we deal with $f(x)=5x+10$. So, we want to show that for $x$ sufficiently large, $f(x)$ can be bounded by $Cx^2$ for some $C$.

To make life simple, let's assume $x\geq 10$, so that $\lvert 5x+10\rvert=5x+10\leq 5x+x=6x$. Now, if $x\geq 10$, then $x\leq x^2$. So, for $x\geq 10$, we have $$ \lvert 5x+10\rvert=5x+10\leq 6x\leq 6x^2. $$ Hence it is true that $5x+10=O(x^2)$, as you were asked.

The big idea with Big-O notation is this: all it asks you to do is to think about the rate of growth of the function, once $x$ is large enough that only leading terms really matter. In this case, the exact order of your function is $x$; for $x\rightarrow\infty$, of course $x^2$ is a faster rate of growth than $x$ is.

Nick Peterson
  • 32,430
1

A related problem. You can use the fact

$$f=O(g)\quad \rm{iff} \quad \limsup_{x \to \infty}\frac{|f(x)|}{|g(x)|} =c,$$

where $c$ is finite.

Community
  • 1
Mhenni Benghorbal
  • 47,431
1

It is as $x \to \infty$. Actually, $5x+10 = o(x^2)$ as $x \to \infty$ (little-oh) since $\lim_{x \to \infty} \frac{5x+10}{x^2} = 0$.

However, $5x+10 \ne O(x^2)$ as $x \to 0$, and $5x \ne O(x^2)$ as $x \to 0$, because there is no real $c$ such that $5x < c x^2$ as $x \to 0$.

Since $x \to 0$ and $x \to \infty$ are the two common limits for big-oh notation, it is important to state which one is meant.

marty cohen
  • 107,799
0

Short answer:
Yes, it is $\mathcal{O}(x^2)$.

Long answer:
Let's look at the definition of $\mathcal{O}$:

$f(x) = \mathcal{O}(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that: $$|f(x)| \le M|g(x)| \text{ for all } x \gt x_0$$

In layman's terms, this is saying that $\mathcal{O}(g(x))$ is an upper bound to the function. Basically, at some point, $g(x)$ grows as fast or faster than $f(x)$.

Clearly, $x^2$ eventually beats out $x$ in terms of growth over the long haul. In the "long haul," (as $x \to \infty$), it doesn't matter what is added to $x$ or what $x$ is multiplied by--$x^2$ will beat it. Thus, $x^2$ is an upper bound.

(This is a non-rigorous argument, of course. Rather than prove it for you, this is just meant to give a feel for how $\mathcal{O}$ works.)

apnorton
  • 17,706