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.
Thanks in advance.
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.
Thanks in advance.
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)$.
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.$