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$$
  • $\begingroup$ 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)}$? $\endgroup$ – Chubbles Mar 24 '16 at 23:50
  • $\begingroup$ @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. $\endgroup$ – String Mar 24 '16 at 23:53

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.