Published on

The Algorithm Design Manual (3rd) Exercise Solution 'E2-45'

Table of Contents

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 2-45

Question

Show that ⌈lg⁡(n+1)⌉=⌊lg⁡n⌋+1\lceil\lg{(n+1)}\rceil=\lfloor\lg{n}\rfloor+1

Solution

[1] With m (m∈Z+m \in \mathbb{Z_+}), n is bound by m as following:

2m≤n<2m+1\begin{equation} 2^m \le n \lt 2^{m+1} \end{equation}

Take logarithm for each hand of (1):

m≤lg⁡n<m+1\begin{equation} m \le \lg{n} \lt m+1 \end{equation}

So, the floor of lg⁡n\lg{n} is mm.

[2] From (1), n+1 is bound as following:

2m<n+1≤2m+1\begin{equation} 2^m \lt n+1 \le 2^{m+1} \end{equation}

Take logarithm for each hand of (3):

m<lg⁡(n+1)≤m+1\begin{equation} m \lt \lg{(n+1)} \le m+1 \end{equation}

So, the ceil of lg⁡(n+1)\lg{(n+1)} is m+1m+1.

[3] From [1] and [2], the following relation is derived.

⌈lg⁡(n+1)⌉=⌊lg⁡n⌋+1⏟the answer=m+1\begin{equation} \underbrace{\lceil\lg{(n+1)}\rceil=\lfloor\lg{n}\rfloor+1}_\text{the answer}=m+1 \end{equation}