# Understanding big $O$ notation.

This was a question on one of my previous exams. Sadly the solutions that were offered in class were torn off and lost at some point over the semester.

Could someone guide me through the solutions to this? I'm strictly doing this for review.

I understand the example from wikipedia here, but the formal definition is a little bit scratchy.

Write down the deﬁnition of $5n + 1 = O(n).$

$$5n + 1 = n \text{ as } n \to \infty$$

$$|5n + 1| \leq Mn \qquad \forall n>n_0$$

How do I go about finding $M$?

Prove that $5n + 1 = O(n)$ is in fact true:

\begin{align*}| 5n + 1| &\leq |5n +1n| \\ |5n + 1| &\leq |6n| \end{align*}

• As you have shown in your case $M=6$ will do the job. In general, $M = 5 + \epsilon$, where $\epsilon > 0$ will do the job since forall $n > \frac1{\epsilon}$, $5n + 1 < (5+\epsilon)n$. – user17762 Dec 14 '11 at 0:04
• Did I properly write the definition? – user17366 Dec 14 '11 at 0:39
• – Did Dec 14 '11 at 10:00

No, that is not the definition.

Definition(Big Ordo): If $b_n$ is a positive sequence we say that a sequence $a_n$ is $O(b_n)$ as $n\to\infty$ provided there is a number $M$ such that $$|a_n|\le Mb_n, \qquad \text{for n>n_0}$$ for some $n_0$.

Remark 1: When it is clear from the context one usually drop "as $n\to\infty$".

Remark 2: I am pretty sad to say that it is pretty common to use the notation $a_n=O(b_n)$ (this is not an equality - it is a property of the sequence $a_n$ with respect to the sequence $b_n$).

Below are some exercises that might help in the understanding of Big Ordo:

1. If $a_n$ is a positive sequence, then $a_n$ is $O(a_n)$ as $n\to\infty$.

2. If $a_n$ is a positive sequence, then $70\cdot a_n$ is $O(a_n)$.

3. If $a_n$ is a positive sequence and $A\in\mathbb{R}$, then $A\cdot a_n$ is $O(a_n)$.

4. Find a counter example to the following statement: If $a_n$ is a positive sequence and $A,B\in\mathbb{R}$, then $A\cdot a_n + B$ is $O(a_n)$.

5. If $a_n=2n$ prove that $a_n$ is $O(n)$.

6. If $a_n=2n$ prove that $a_n$ is $O(n^2)$.

7. If $a_n=2n$ and $\varepsilon>0$, prove that $a_n$ is not $O(n^{1-\varepsilon})$.

8. If $a_n>0.05$ then $5a_n +1$ is $O(a_n)$.