Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
It is well known that at height $i$ the number of nodes is bounded by $ \frac{n}{2^{i+1}} $, for example there are at most $n/2$ leafs.
Now, it makes sense only if we're taking $ \left\lceil \frac{n}{2}\right\rceil $, because for example, a binary tree with $7$ nodes has $4$ leafs at most.
My question is: why do we take $ \left\lceil \frac{n}{2}\right\rceil $ and not $ \left\lfloor \frac{n}{2}\right\rfloor $?
Asympotically, isnt it safer to assume we have more nodes then there actually are?
We use $\lceil \frac{n}{2} \rceil$ instead of $\lfloor \frac{n}{2} \rfloor$ since our task is to find an upper bound.
To understand this, lets take for example two real positive numbers $0<x<y$. In this expression, $y$ is an upper bound for $x$, but is not necessarily a whole number. However, both $\lceil y \rceil$ and $\lfloor y \rfloor$ are whole numbers. We still want to retain a similar bound, but now using $\lceil y \rceil$ or $\lfloor y \rfloor$ instead of $y$.
Note, that $y\le \lceil y \rceil$, and therefore $x<y\le \lceil y \rceil$ and thus $\lceil y \rceil$ is an upper bound.
But $\lfloor y \rfloor \le y$, and thus it is not necessarily true that $x < \lfloor y \rfloor $. For example, $x=0.5,y=0.75$ will be a counter-example, since $\lfloor y \rfloor=0 < x$.
Therefore, for correctness we must use the ceiling for upper bounds. Similarly, for lower bounds we will use the floor instead.
As a side note, asymptotically taking a ceiling is equivalent to taking a floor, since they must both be at most distance $1$ from each other: $\lceil y \rceil \le \lfloor y \rfloor + 1$.
