Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers

up vote 4 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|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
add comment

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|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
add comment

Your Answer

 
discard

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.