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:
- 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.
- 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?