0
$\begingroup$

I need to learn how to prove/disprove each of the following. Anyone able to do it in very simple way for a NON -mathematician to easily understand? ( NB -- NOT HOMEWORK)

a) $n^2 + n + 1 = \Theta (n^2)$ b) $ n^2 = \omega(2^n)$ c) $n^2 = o (2^n)$ d) $\left|n \sin {\pi\cdot n\over 2}\right| = \Theta(n)$

2 Answers 2

2

For all sufficiently large $n$, $n^2 < n^2 + n + 1 < 2n^2$. Hence 1) is true.

For any positive $k$, $n^2 < k2^n$ for all sufficiently large $n$. Hence 2) is not true (whether with $\omega$ or $\Omega$).

Given any $\varepsilon > 0$, $0 < n^2/2^n < \varepsilon$ for all sufficiently large $n$. Hence 3) is true.

Finally, 4) is not true, since $n\sin (\pi n/2) = 0$ for infinitely many (positive integers) $n$.

  • 0
    oooh!! I see it now! thanks2011-07-11
2

(n.b.: for all definitions I'm taking the Wikipedia version as gospel)

For (a): you need to show that there are constants $k_1$ and $k_2$ such that $k_1\cdot n^2 \leq n^2+n+1 \leq k_2\cdot n^2$ for all sufficiently large $n$ - or in other words, dividing through by $n^2$, constants $k_1$ and $k_2$ such that $k_1 \leq 1+{1\over n}+{1\over n^2} \leq k_2$ for all sufficiently large $n$. Try plugging in some values of $n$ and you should be able to make a reasonable hypothesis about the behavior of the term in the middle; this will give you your bounds.

The others follow rather similarly - except for (d), which by the Wikipedia definition is actually false as written. Hint: what are the values on the left hand side? Can you show that there is no positive $k_1$ such that $\left|n\sin(\pi\cdot n/2)\right|\geq k_1n$ for all sufficiently large $n$?