Trying to prove or disprove this (pretty sure it's correct):
Let $\mathcal{F}=\{f\mid f:\mathbb{N}\to\mathbb{R}^+\}$
$$\forall f\in\mathcal{F}: \left\lfloor \sqrt{\lfloor f(n)\rfloor }\right\rfloor \in O\left(\sqrt{f(n)}\right)\;.$$
How can I get rid of both of the floor functions? Because I think that'll make it simpler
Progress: Now I am trying to prove $\lfloor \sqrt{\lfloor x)\rfloor }\rfloor = \lfloor \sqrt{x} \rfloor$ which will then make the rest of proof pretty easy.
Right now I have:
$$Let \ k = \lfloor \sqrt{\lfloor x\rfloor }\rfloor$$
$$Then \ k \le \sqrt{\lfloor x\rfloor } < k +1$$
$$Then \ k^2 \le \lfloor x\rfloor < (k+1)^2$$
But I am not too sure how to reach a point where it says
$$k \le \sqrt[]{x} < k+1$$
Which is the definition of floor function and conclude they are equal
Best Answer
In general, for $x\geq 0$, $\lfloor\sqrt{\lfloor x\rfloor}\rfloor \leq \sqrt{x}$.
This follows because $\lfloor z\rfloor \leq z$ and $\sqrt{z}$ is an increasing function.