# Calculating Running Time 101

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

-

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

-
Where did you get 2 from? $n$, $n^2 < n^2 + n + 1 < 2n^2$. – user10695 Jul 11 '11 at 21:50
@user10695: We want to show that there exist positive constants $k_1$ and $k_2$ such that $k_1 n^2 \leq n^2 + n + 1 \leq k_2 n^2$ for all sufficiently large $n$. This obviously holds with $k_1 = 1$, and it is easy to see that this holds with $k_2 = 2$, noting that $n+1 < n^2$ for all sufficiently large $n$ (actually, for all $n \geq 2$). – Shai Covo Jul 11 '11 at 22:03
oooh!! I see it now! thanks – user10695 Jul 11 '11 at 22:56

(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$?

-