Answer to Question #260078 in Algorithms for kriti

Question

Prove weather following statements are true or false.

1. 7n3+n2 ≠ Ω(n4)
2. 9n + 3 = O(n2)
3. n*lgn + 8n2 = Ω(n3)
4. 2n + n3 + 1 = Ө(n3)

Answer 1

$f(n)=O(g(n))$ if there exists a positive real number M and a real number n₀ such that

$|f(n)|\le Mg(n)$ for $n\ge n_0$

$f(n)=\Omega(g(n))$ if there exists a positive real number M and a real number n₀ such that

$|f(n)|\ge Mg(n)$ for $n\ge n_0$

$f(n)=\theta(g(n))$ if there exists a positive real numbers M₁ and M₂ and a real number n₀ such that

$M_1g(n)\le|f(n)|\le M_2g(n)$ for $n\ge n_0$

1.

$7n^3+n^2\le 8n^3$

$8n^4\ge 8n^3\ge7n^3+n^2$

2.

$9n+3\le 12n$

$12n^2\ge 12n \ge 9n+3$

3.

$n^3\le nlgn+8n^2$

4.

$n^3\le 2n+n^3+1\le 4n^3$