1
$\begingroup$

I was reading some algorithm's analysis and I came across the following in the proof:

$\log_2(n+1) \le h \le 1 + \log_2(n) \implies h = \lceil \log_2(n+1)\rceil$

Here both $h$ and $n$ are integral. Why is the above true ?

  • 1
    Hint: log_2(n) So log_2(n). How many different integers $h$ can be in the range $(x,x+1]$ for any real number $x$? And is $\lceil \log_2(n+1)\rceil$ in that range when $x=log_2(n)$?2011-10-28

1 Answers 1

4

The ceiling function $\lceil x\rceil$ can be defined as the unique integer in the interval $[x,x+1)$.
But $1+\log_2(n)< 1+\log_2(n+1)$, so $h$ is an integer in the interval $[\log_2(n+1),1+\log_2(n+1))$. That means that $h=\lceil \log_2(n+1)\rceil$.