# A function that is neither O(n) nor Ω(n).

I think I have a function like this, $$f(n) = (1 + \sin n) \cdot 2^{2^{n+2}}.$$

But I'm not entirely sure of how to prove this. If anyone can think of a better function, please go ahead I would greatly appreciate it.

-

Let $f(n)=n^2$ for $n$ even. This is enough to make sure $f$ is not $O(n)$.

Let $f(n)=0$ for $n$ odd. This is enough to make sure $f$ is not $\Omega(n)$.

-
thanks for your reply, any specific way to prove it? – AlanTuring Sep 19 '12 at 22:17
Which of my statements are you having trouble proving? – Chris Eagle Sep 19 '12 at 22:21
nevermind, i think i got it thanks again to you. – AlanTuring Sep 20 '12 at 0:16

A function $f(n)\in O(n)$ if it is eventually less than $kn$ for some $k>0$; so $f(n)\not\in O(n)$ if it exceeds $kn$ at arbitrarily large values of $n$ for every $k>0$. Similarly, $f(n)\not\in\Omega(n)$ if it is less than $kn$ at arbitrarily large values of $n$ for every $k>0$. So a function $f(n)$ is neither $O(n)$ nor $\Omega(n)$ as long as $f(n)/n$ swings both above and below any fixed range $[a,b]$ for arbitrarily large values of $n$. An example is any function that oscillates between $1$ and $n^2$, e.g., $$f(n)=\cos^2 n + n^2\sin^2 n.$$

-
thanks so much, that seems to be exactly correct, any advice on how to go about proving it, or should the reasoning you provided be enough? – AlanTuring Sep 19 '12 at 22:17
@mjqxxxx: This is a correct example. It requires some extra work to show that there are arbitrarily large integers $n$ such that $\sin n$ is not near $0$. Replacing $\sin n$ by $\sin \frac{n\pi}{2}$ makes verification much easier. – André Nicolas Sep 19 '12 at 22:33
thank you so much for your example, your reasoning is perfect however i think i would be better off using an example that i can relate with more readily and explain in a slightly more easy fashion. – AlanTuring Sep 20 '12 at 0:18