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

4

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
    thanks for your reply, any specific way to prove it?2012-09-19
  • 0
    Which of my statements are you having trouble proving?2012-09-19
  • 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
    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?2012-09-19
  • 0
    @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.2012-09-19
  • 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