# Asymptotic analysis

• Mar 16th 2009, 03:51 PM
Apprentice123
Asymptotic analysis
Which of the following conjecture is true? Justify

10n = O(n) $\displaystyle 10n^2 = O(n)$ $\displaystyle 10n^{55} = O(n^2 )$

1) $\displaystyle 10n \leq cn$ => $\displaystyle n=1$ $\displaystyle c=10$

$\displaystyle f(n) \leq 10g(n)$ for all $\displaystyle n \geq 1$. $\displaystyle f(n) \in O(g(n))$

How can I solve the other two?

I found this problem on the Internet:
It is true that $\displaystyle n^2 + 200n + 300 = O(n^2 )$ ? And $\displaystyle n^2 -200n -300 = O(n)$ ?
• Mar 16th 2009, 11:32 PM
matheagle
I don't know what you mean by n2?
Is that 2 times n or a sequence $\displaystyle n_2$?

O(n) just means that the term is bounded about when divided by n,
limsup is finite.
• Mar 17th 2009, 08:28 AM
Apprentice123
Now the order of the exercise is correct
• Mar 17th 2009, 01:15 PM
matheagle
DIVIDE by $\displaystyle n^2$ and n and take the limits.

Quote:

Originally Posted by Apprentice123
Which of the following conjecture is true? Justify

10n = O(n) $\displaystyle 10n^2 = O(n)$ $\displaystyle 10n^{55} = O(n^2 )$

1) $\displaystyle 10n \leq cn$ => $\displaystyle n=1$ $\displaystyle c=10$

$\displaystyle f(n) \leq 10g(n)$ for all $\displaystyle n \geq 1$. $\displaystyle f(n) \in O(g(n))$

How can I solve the other two?

I found this problem on the Internet:

It is true that $\displaystyle n^2 + 200n + 300 = O(n^2 )$
YES

And $\displaystyle n^2 -200n -300 = O(n)$
NO

• Mar 17th 2009, 02:16 PM
Apprentice123
Sorry, I do not understand
• Mar 17th 2009, 03:36 PM
Apprentice123

1.1) $\displaystyle 10n \leq cn$ => $\displaystyle n \geq 1$ and $\displaystyle c \geq 10$

1.2) $\displaystyle 10n^2 \leq cn^2$ $\displaystyle n \geq 1$ and $\displaystyle c \geq 10$

1.3) $\displaystyle 10n^{55} \leq c2^n$

$\displaystyle \frac{10n^{55}}{2^2} \leq c$ How can I continue?

2.1) $\displaystyle n^2+200n+300 \leq cn^2$

$\displaystyle 1+\frac{200}{n}+\frac{300}{n^2} \leq c$

$\displaystyle n \geq 1$ and $\displaystyle c \geq 501$

2.2) $\displaystyle n^2-200n-300 \leq cn$

$\displaystyle n-200-\frac{300}{n} \leq c$ How can I continue?

What I done is correct?