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

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)$

Solutions Collecting From Web of "Determine whether $F(x)= 5x+10$ is $O(x^2)$"

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.

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.

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.

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.)