Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
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.$$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.