Intereting Posts

Relationship between l'Hospital's rule and the least upper bound property.
Ordinal arithmetic exercise in Kunen
Continuity of a monotonically increasing function
Value of $\lim_{n\to \infty}\frac{1^n+2^n+\cdots+(n-1)^n}{n^n}$
Help with Induction problem?
Number of transitive acting groups on four letters?
Why is the rational number system inadequate for analysis?
Proof of lack of pure prime producing polynomials.
Simple inequality for measures
Uniform Continuity of $f(x)=x^3$
Determining the coefficients of the reciprocal of a Dirichlet series
Rank of the $n \times n$ matrix with ones on the main diagonal and $a$ off the main diagonal
When does the boundary have measure zero?
The set of all $x$ such that $xHx^{-1}\subseteq H$ is a subgroup, when $H\leq G$
How do we construct the coslice category $C / \bf{C}$ given $\textbf{C}/C$ and prove that the two are equal?

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

- A conditional asymptotic for $\sum_{\text{$p,p+2$ twin primes}}p^{\alpha}$, when $\alpha>-1$
- Is $\log(n!) \in\Theta(n \log n)$
- Mean of fractional part of $\log n$
- Using Limits to Determine Big-O, Big-Omega, and Big-Theta
- Asymptotic expansion of $\int_{0}^{\infty} \frac{\sin(\frac{x}{n})}{x(1+x^2)}dx$?
- Asymptotic expansion of the complete elliptic integral of the first kind

- $A \oplus B = A \oplus C$ imply $B = C$?
- How to prove reflexivity, symmetry and transitivity for the following relation?
- Proving that any common multiplication of two numbers is a multiplication of their least common multiplication
- Solving recurrence relation?
- Chain rule for discrete/finite calculus
- Giving an asymptotically tight bound on sum $\sum_{k=1}^n (\log_2 k)^2$
- Iterated sums and asymptotics
- Bounds on $\sum_{k=0}^{m} \binom{n}{k}x^k$ and $\sum_{k=0}^{m} \binom{n}{k}x^k(1-x)^{n-k}, m<n$
- Maximum board position in 2048 game
- How many 4-element subsets of a given set contain no consecutive integers

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

- Irreducibility issue
- Intuition behind Matrix Multiplication
- I don't understand how sets can be closed, yet disjoint?
- How find all ordered pairs $(m,n)$ such $\frac{n^3-1}{mn-1}$ is an integer
- Lebesgue inner measure formula
- Problems about Countability related to Function Spaces
- Why does $\int_a^b fg\, dx = 0$ imply that $f = 0$?
- Proof By Induction – Factorials
- metric property in a group
- Class Group of $\mathbb{Q}(\sqrt{-47})$
- Are the axioms for abelian group theory independent?
- On constructing a triangle given the circumradius, inradius, and altitude .
- $\mathcal{B}^{-1}_{s\to x}\{e^{as^2+bs}\}$ and $\mathcal{L}^{-1}_{s\to x}\{e^{as^2+bs}\}$ , where $a\neq0$
- What is wrong with treating $\dfrac {dy}{dx}$ as a fraction?
- Non-measurable set in product $\sigma$-algebra s.t. every section is measurable.