Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 definition 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*}$$

share|improve this question
2  
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
    
Related answer. –  Did Dec 14 '11 at 10:00
add comment

1 Answer 1

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.