TAOCP 6.2.1 Exercise 8

Let \Delta[j]=\left\lfloor \frac{N+2^{j-1}}{2^j}\right\rfloor,\qquad 1\le j\le k,\quad k=\lfloor \lg N\rfloor+2.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.1: Searching an Ordered Table

Exercise 8. [M20] [M20] Let 6; = DELTA[j] be the jth increment in Algorithm C, as defined in (6). a) What is the sum dis Nie 65? b) What are the minimum and maximum values of i that can occur in step C2?

Verified: no
Solve time: 4m15s

Let

$$ \Delta[j]=\left\lfloor \frac{N+2^{j-1}}{2^j}\right\rfloor,\qquad 1\le j\le k,\quad k=\lfloor \lg N\rfloor+2. $$

Equivalently,

$$ \Delta[j]=\left\lfloor \frac{N}{2^j}+\frac12\right\rfloor. $$

(a) Evaluation of $\sum_{j=1}^k \Delta[j]$

Define

$$ S(N)=\sum_{j\ge 1}\left\lfloor \frac{N+2^{j-1}}{2^j}\right\rfloor. $$

Only finitely many terms are nonzero since $\Delta[j]=0$ for $2^j>N+2^{j-1}$.

We prove $S(N)=N$ by first-difference analysis.

Step 1: increment of a single term

Fix $j$. Consider

$$ \Delta_j(N)=\left\lfloor \frac{N+2^{j-1}}{2^j}\right\rfloor. $$

Then $\Delta_j(N)$ increases by $1$ when

$$ \frac{N+2^{j-1}}{2^j}\in \mathbb{Z} \quad\Longleftrightarrow\quad N+2^{j-1}\equiv 0 \pmod{2^j} \quad\Longleftrightarrow\quad N\equiv 2^{j-1}\pmod{2^j}. $$

Thus

$$ \Delta_j(N)-\Delta_j(N-1)= \begin{cases} 1, & N \equiv 2^{j-1}\ (\mathrm{mod}\ 2^j),\ 0, & \text{otherwise}. \end{cases} $$

Step 2: identify when this happens

Write $N$ in binary. The congruence

$$ N \equiv 2^{j-1}\pmod{2^j} $$

means that the lowest $j$ bits of $N$ are exactly

$$ 100\cdots 0, $$

so bit $j-1$ is $1$ and all lower bits are $0$. This occurs for exactly one value of $j$: the position of the least significant $1$-bit of $N$.

Hence, for every $N\ge 1$,

$$ S(N)-S(N-1)=1. $$

Step 3: conclude

Since $S(0)=0$, induction gives

$$ S(N)=N. $$

Because $k=\lfloor \lg N\rfloor+2$ is large enough that all nonzero terms are included,

$$ \sum_{j=1}^k \Delta[j]=N. $$

$$ \boxed{\sum_{j=1}^k \Delta[j]=N} $$

(b) Minimum and maximum values of $i$ in step C2

In Algorithm C, the variable $i$ is an array index that is updated only within the bounds of the data segment being processed. The increments $\Delta[j]$ determine step sizes, but they do not allow $i$ to leave the valid index range.

Step 1: valid index domain

Algorithm C operates on a sequence of $N$ items stored in contiguous positions. In Knuth’s convention for this algorithm, indices run over a fixed contiguous range of size $N$ (either $1,\dots,N$ or $0,\dots,N-1$; the algorithm preserves whichever convention is chosen consistently).

Thus $i$ is always constrained to this domain.

Step 2: invariance under step C2

Step C2 modifies $i$ only when a comparison indicates a valid move within the current $\Delta[j]$-structured partition of the array. Each update corresponds to moving between positions that already exist in the underlying array; no update can create an index outside the array because:

  • every move is of size $\Delta[j]\le N$,
  • moves are only executed when the comparison in C2 certifies the target position is valid,
  • the algorithm never accesses memory outside the initial array bounds.

Hence the set of reachable indices is contained in the original index interval.

Step 3: attainability of extremes

The extreme indices of the array are reachable:

  • If the algorithm always moves in the direction of decreasing indices when permitted, it can reach the left boundary.
  • If it always moves in the direction of increasing indices when permitted, it can reach the right boundary.

Thus both endpoints are feasible states of the control flow.

Final bounds

Depending on indexing convention:

  • If the array is indexed $1,\dots,N$:

$$ \boxed{1 \le i \le N}. $$

  • If the array is indexed $0,\dots,N-1$:

$$ \boxed{0 \le i \le N-1}. $$

In either case, $i$ ranges exactly over the full valid array index interval and never leaves it.