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: