2
$\begingroup$

I'm working on my data structures homework and proving Big O and Big Theta for a couple questions. After choosing my values for C and getting to the end I'm left with the fraction 1/300 for $N_0$ for both Big O and Big Theta. I understood from lecture that we actually take the ceiling of the fraction for Big O, making it 1. My question is, do I also take the ceiling of Big Theta, or would it be the floor? Since Big Theta is a lower-bound.

$\endgroup$
1
$\begingroup$

The reason we take floor or ceiling at all in this context is that the definition asks for an integer $N_0$. Now the definitions of big $O$ and big $\Theta$ are both of the form

There exists a real constant $C > 0$ and an integer constant $N_0$ such that for all $n \geq N_0$, the following holds: ...

Let us denote what should hold by $P(n)$. If you have shown that $P(n)$ holds for all $n \geq N_0$, then it follows that it holds for all $n \geq \lceil N_0 \rceil$ as well, since if $n \geq \lceil N_0 \rceil$ then also $n \geq N_0$. It doesn't necessarily follow that $P(n)$ holds for all $n \geq \lfloor N_0 \rfloor$, since if $N_0$ is not an integer, $\lfloor N_0 \rfloor \not \geq N_0$.

| cite | improve this answer | |
$\endgroup$

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.