Assuming $f(n)$ is non-decreasing and $f(n) = n^2$ where $n$ is odd, then $f(n) \in \Theta(n^2)$.

226 Views Asked by At

Assuming $f(n)$ is a non-decreasing function and $f(n) = n^2$ where $n$ is odd, then $f(n) \in \Theta(n^2)$ i.e. $\exists c_1, c_2, n_0 \in \mathbb{R^{\geq 0}}, \forall n \in \mathbb{N}, n > n_0 \Rightarrow c_1 \cdot n^2 \leq f(n) \leq c_2 \cdot n^2 $. How do I go about this proof given assuming we only know that when $n$ is odd and nothing is given for when it is even. Is it possible to prove this using the floor function?

Any help would be appreciated and if you could prove this using the floor function especially, it would help me understand how to prove Big-Theta proofs.