2
$\begingroup$

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.

2 Answers 2

5

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

  • 0
    nevermind, i think i got it thanks again to you.2012-09-20
1

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

  • 0
    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.2012-09-20