# Correctness of Idea of Big O Proof

I have this big O proof and was wondering about the correctness of my rough work. Could anyone confirm if my idea for my proof is correct?

Here is the question: Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$

$\forall f\in\mathcal{F}: \lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \in O(\sqrt{f(n)}).$

And here's the def of Big O I used:$f(n)\in\mathcal{O}(g(n))\iff \exists c \in \mathbb{R^+}: \exists B \in \mathbb{N}: \forall n \in \mathbb{N}, n \ge B \implies f(n) \le cg(n)$

So basically I just manipulated the floor definition.

$\lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \iff \sqrt{\lfloor f(n)\rfloor } - 1 < \lfloor \sqrt{\lfloor f(n)\rfloor } \rfloor \le \sqrt{\lfloor f(n)\rfloor }$ and since $\lfloor f(n)\rfloor \le f(n)$ then $\sqrt{\lfloor f(n)\rfloor } \le \sqrt{f(n)}$

So $\lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \iff \sqrt{\lfloor f(n)\rfloor } - 1 < \lfloor \sqrt{\lfloor f(n)\rfloor } \rfloor \le \sqrt{\lfloor f(n)\rfloor } \le \sqrt{f(n)} \le c\sqrt{f(n)}$ (The c from the Big O def) So $\lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \le c\sqrt{f(n)} \therefore \lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \in O(\sqrt{f(n)})$

Is that ok? Is that the correct path to go? Obviously I still need to choose some constant c and breakpoint B.

You write some confusing stuf. One thing is that your notation is incorrect since $$\lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \iff \text{something}$$ does not make sense because $\lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor$ is an algebraic expression, not a statement that can hold a boolean value as either True or False.
When arguing that $$\lfloor \sqrt{\lfloor f(n)\rfloor }\rfloor \leq 1\cdot \sqrt{f(n)}\quad,\qquad\forall n\in\mathbb N:n\geq 1$$ which BTW tells us that $c=B=1$ will work as constant factor and breakpoint respectively, you will need the following statements:
• $\lfloor t\rfloor\leq t$ for all $t\in\mathbb R$
• $\sqrt{t}$ is an increasing function so it preserves inequalities. Namely, for all $a,b\in\mathbb R^+$: $$a<b\iff\sqrt a<\sqrt b$$
• I used the iff because the floor gives me some natural number that satisfies the inequality beside. Other than that, I get what you're saying. But is my idea for how the proof goes ok? Like basically $\lfloor \sqrt{\lfloor f(n)\rfloor } \rfloor \le \sqrt{\lfloor f(n)\rfloor } \le \sqrt{f(n)} \le c\sqrt{f(n)}$? – Chubbles Mar 24 '16 at 23:50
• @Chubbles: Yes, those steps are correct! Only I would replace $c$ by $1$ immediately and argue using the two propositions I gave to qualify each step. – String Mar 24 '16 at 23:53