0
$\begingroup$

I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$

Here's what I've thought of so far, we can set C = 10 and k = 1 and somehow prove that this would eventually dominate the function? Not sure how I can prove this without a concrete function defined for $f$

According to the definition of big O, enter image description here

For any C larger than 1, C times floor of f would eventually dominate f. What I can't figure out is how to outline this in a formal proof. Any help is appreciated!

$\endgroup$
1
  • $\begingroup$ I rewrote my answer in a much simpler way. $\endgroup$
    – user16034
    Commented Nov 23, 2022 at 9:35

1 Answer 1

1
$\begingroup$

$$\{f\}<1\le\lfloor f\rfloor\implies f=\lfloor f\rfloor+\{f\}<2\lfloor f\rfloor.$$


Together with $2\lfloor f\rfloor\le2f$, that makes $f=\Theta(\lfloor f\rfloor)$.

enter image description here

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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