Upper and Lower Bounds Proof for Positive Functions

722 Views Asked by At

Is it true that for some function $f:N\to N$, a positive function, then either one of these conditions hold. First is that there is some $a>0$, such that $f(n)\in O(n^a)$. Or Second, there is some $b>1$ such that $f(n)\in\Omega(b^n)$.

So what I understand from this is that $O$ is like the upper bound and $\Omega$ is the lower bound. So now, if we have some positive function say $f(n)=\log(n)$, then one of these conditions always holds? Doesn't the first condition hold for $\log$? Is there a way to prove this for any positive function?

1

There are 1 best solutions below

3
On

No, that is not true -- a counterexample would be $$ f(n) = \begin{cases} 1 & n\text{ odd} \\ 2^n & n\text{ even} \end{cases}$$

With a bit more work one can construct strictly increasing examples too, such as this recurrence: $$ f(0)=1 \qquad f(n+1) = \begin{cases} 2^n & \text{if }f(n)\le 2n \\ f(n)+1 & \text{otherwise} \end{cases} $$