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