0
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ Confused by your question upon rereading. You first motivate that the ceiling function is the correct answer and then ask why the ceiling function is used. Did you mean to write about the floor function instead? $\endgroup$
    – Michel
    Dec 15, 2021 at 19:16
  • $\begingroup$ The number of nodes is not bounded by $\frac{n}{2^{i+1}}$. Simply substitute $i=\log(n)$ and you already get that there are at most $2$ nodes at this level (which is obviously wrong, there may be a lot more). The correct term that bounds this is just $2^i$: each new level may increase the number of nodes by at most two (since every node may have at most two children). $\endgroup$
    – nir shahar
    Dec 15, 2021 at 20:25
  • $\begingroup$ @nirshahar Actually it sounds correct that at the height $\log(n)$ there would be at most 2 nodes. Maybe your'e confusing height and depth? by height =0, for example, I mean the leafs (and your expression obviously gives wrong answer). $\endgroup$
    – FreeZe
    Dec 15, 2021 at 21:10
  • $\begingroup$ Oh, then that is right. If you meant that height $0$ are leaves then yes. I thought you meant that height $0$ is the root :o $\endgroup$
    – nir shahar
    Dec 15, 2021 at 22:22

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

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

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