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 ?

  • 0
    Should the logarithm on the right be logarithm base 2?2011-10-28
  • 0
    yes ! thanks for noticing2011-10-28
  • 1
    Hint: $log_2(n)$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$.