In class we are currently covering upper/lower bounds, big Oh and omega and the like. I am pretty good on the "typical" functions one would do, but at a complete loss at "general" statements. This ons function, for example:
$$\forall f\in\mathcal{F}: \lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \in O(\sqrt{f(n)}).$$
the domain F by the same is all natural numbers that return a real positive number when inputted. My first instinct with something like this is to remove the floors, the general strategy I though to solve this is remove the outer floor, then get rid of the square root, and then the inner floor. But I have no idea how to go about this or if this is even the right way to do it.
Help please? Thanks in advance.
When $x\geq 0$ we have $0\leq Floor(x)\leq x\;,$ so $\;0\leq Floor (\sqrt {Floor(x)}\;)\leq \sqrt {Floor (x)}\leq \sqrt x.$ $$ \text {Now }\quad g(x)=O(h(x)) \iff \exists k>0\;\exists r\; (\;x>r\implies |g(x)|\leq k|h(x)|\;).$$ Apply this with $r=0,k=1,g(x)=Floor (\sqrt {Floor (f(x))}\;)$ and $h(x)=\sqrt {f(x)}.$
Note: You often see $g(x)=O(h(x))$ as a synonym for $g(x)\in O(h(x)).$