# Show that functions in O(1) can't grow faster than their composition with themselves

Let $f(n)$ be a function s.t $f(n)\geq 1$ for every $n$.

I want to disprove that if $f(n) = \omega (f(f(n)))$ then it means that $f(n) = O(1)$.

I thougt of 2 approaches to show that this statement is incorrect:

1. Give an Example of a function that $f(n) = \omega (f(f(n)))$ for it,

for example: $f(n) = \sqrt n$

and then I'm supposed to get a contradiction, and show that $\sqrt n \neq O(1)$ but that's the step I'm stuck at, but I'm not sure how that contradiction is derived. I mean formally, because I understand it by intuition.

1. Start with the function that suffice $f(n) = O(1)$ and then show that it's impossible to get the condition under that function (It's sort of going from the end to the beginning)

what's the right approach and how do I get it right?

• If you want to disprove your statement, you just have to give an example, where the statement does not hold. So your example $\sqrt{n}$ is perfect. To prove $\sqrt{n}\notin O(1)$, you just have to look at the definition of $O(1)$. – Danny Nov 5 '14 at 18:21
• There is no "right approach". Any approach that works is "right". – Yuval Filmus Nov 5 '14 at 18:32
• This is a pure mathematics question as it is. What is the reason it is here; does it have applications in CS or do you need specific computer science expertise? That said, note that your first approach has been covered at our reference question. For the second variant, hint: pick an arbitrary $f \in \Theta(1)$. (Do you see why no others can occur here?). Compare $f$ and $f \circ f$. – Raphael Nov 5 '14 at 19:39

To complete the first approach and show that $\sqrt{n}\notin O(1)$, you just need to show that the statement "There exist constants $c$ and $n_0$ such that, for all $n\geq n_0$, $\sqrt{n}\leq c\cdot1$" is false. That is, you need to show that, for any $c$ and $n_0$, there is an $n\geq n_0$ such that $\sqrt{n}>c$. For example, you can take $n=n_0+c^2$ (or $\max\,\{n_0,c^2\}$, if you prefer).
I don't really understand your second approach. If $f(n)=O(1)$, it's perfectly possible that $f(n)\in \omega(f(f(n)))$: take any constant function, for example.
Regarding the second approach, suppose that $f(n) = O(1)$. Then for some $C \geq 1$, $f(n) \leq C$ for all $C$. On the other hand, since $f(n) \geq 1$, we have $f(f(n)) \geq 1$. Therefore $f(n) \leq Cf(f(n))$, implying that $f(n) = O(f(f(n)))$. In particular, it is not the case that $f(n) = \omega(f(f(n)))$.
Note, however, that this doesn't disprove the claim you were interested in. Let $P(f)$ be the property that $f(n) = \omega(f(f(n))$, and let $Q(f)$ be the property that $f(n) = O(1)$. Also, let $F$ be the set of functions $f$ such that $f(n) \geq 1$ for all $n$. The claim you want to disprove is $$\forall f \in F, P(f) \Rightarrow Q(f).$$ The negation of this claim is $$\exists f \in F, P(f) \text{ and not } Q(f).$$ Your second approach instead shows that $$\forall f \in F, Q(f) \Rightarrow \lnot P(f).$$ This does not disprove the original claim. For example, it might be the case that $P(f)$ is always false, and then the original claim would actually be correct.