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


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.

| cite | improve this answer | |
  • $\begingroup$ Well we can say that ⌊f(n)⌋ <= f(n), but how can we introduce the square root after this and finally the floor of the last one? Thanks $\endgroup$ – Amir Mousavi Mar 25 '16 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.