Asymptotic analysis

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

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

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

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

How can I solve the other two?

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

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

Quote:

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

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

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

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

How can I solve the other two?

I found this problem on the Internet:

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

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

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

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

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

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

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

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

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

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

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

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

What I done is correct?