Time complexity of the ceiling

Question

I was reading a paper that mentioned that O($\lceil \sqrt{n}\rceil ) $ and O($\sqrt{n}$) were both big theta of each other. Does that mean that the ceiling does not have much of an effect on the time complexity of a function? I can't seem to find much information on this.

Answer 1

It means that there's a positive constant $M$ and a positive constant $c$ with the property that for all $n > M$, we have

$$ \lceil \sqrt{n}\rceil \le c \sqrt{n} $$

and a second pair of constants $M', c'$ with the property that for all $n > M'$, $$ \sqrt{n} \le c' \lceil \sqrt{n}\rceil . $$

Let's see why the first one is true. Well, I'm going to pick $M = 4$ and $c = 2$, and show that for all $n > 4$, $\lceil \sqrt{n}\rceil \le c \sqrt{n}$. Here goes. Suppose $n > 4$. \begin{align} \sqrt{n} &> n & \text{ because $n \mapsto \sqrt{n}$ is an increasing function on the positive reals}\\ n &> 1 &\text{because $n > 4$}\\ \sqrt{n} &> 1 & \text{previous two statements}\\ 1 &< \sqrt{n} \\ \sqrt{n} + 1 &< 2 \sqrt{n} & \text{Add $\sqrt{n}$ to both sides} \\ \lceil \sqrt{n} \rceil &< \sqrt{n}+1 & \text{Definition of "ceiling"}\\ \lceil \sqrt{n} \rceil &< 2\sqrt{n} & \text{Previous two statements}\\ \end{align} and we are done.

For the second part, which I'm going to leave to you to write out, the choices $M' = c' = 1$ suffice, and the critical thing you need is that $$x \le \lceil x \rceil $$ for any $x$, and particularly for $x = \sqrt{n}$.

The main thing to realize here is that the time taken to compute the "ceiling" in a computer program is completely irrelevant; this is a statement about real-valued functions on the positive integers.

Answer 2

This means that when you have a function $f$ with

$$\limsup_{n\to\infty}\left|\frac{f(n)}{\lceil \sqrt n \rceil}\right|=C\in\Bbb R$$

then also

$$\limsup_{n\to\infty}\left|\frac{f(n)}{\sqrt n}\right|=C\in\Bbb R$$

and vice versa. Or in words: if a function $f$ grows asymtotically like $\lceil\sqrt n\rceil$, then it also grows asymtotically like $\sqrt n$ (and vice versa) and it therefore makes not much sense to include the ceiling function in the description of a complexity class. No matter if you write $\mathcal O(\lceil \sqrt n \rceil)$ or $\mathcal O(\sqrt n)$, both describe the exact same class of functions.

I am not sure if your question was meant that way, but this obervation does say nothing about the complexity of computing the ceiling functions!