TAOCP 6.2.1 Exercise 5

We restart from the correct inequality and determine the full integer solution set carefully.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.1: Searching an Ordered Table

Exercise 5. [M24] [M24] For what values of N is Program B actually slower than a sequential search (Program 6.1Q’) on the average, assuming that the search is successful?

Verified: yes
Solve time: 2m29s

We restart from the correct inequality and determine the full integer solution set carefully.

Let

$$ T_B(N) = (18 \lg N - 16)u, \qquad T_S(N) = \frac{N+1}{2}u. $$

Program B is slower on average exactly when

$$ 18 \lg N - 16 > \frac{N+1}{2}. $$

Multiplying by $2$,

$$ 36 \lg N - 32 > N+1, $$

hence

$$ f(N) = 36 \lg N - 33 - N > 0. $$

We determine all integers $N \ge 1$ satisfying this inequality.

1. Small values

We first check the lower boundary behavior.

For $N=1$,

$$ f(1) = 36 \lg 1 - 33 - 1 = -34 < 0. $$

For $N=2$,

$$ f(2) = 36 \lg 2 - 33 - 2 = 36 - 35 = 1 > 0, $$

since $\lg 2 = 1$.

Thus $N=1$ is not a solution, but $N=2$ is.

2. Shape of the function

Extend $f$ to a real variable $x \ge 1$:

$$ f(x) = 36 \lg x - 33 - x. $$

Its derivative is

$$ f'(x) = \frac{36}{x \ln 2} - 1. $$

This satisfies:

  • $f'(x) > 0$ when $x < \frac{36}{\ln 2}$,
  • $f'(x) < 0$ when $x > \frac{36}{\ln 2}$.

Since

$$ \frac{36}{\ln 2} \approx 51.9, $$

the function $f(x)$ is strictly increasing up to about $x \approx 52$, and strictly decreasing thereafter. Hence $f(x)$ has a single maximum and crosses any horizontal level at most twice.

Therefore, the inequality $f(N) > 0$ holds for a single contiguous interval of integers.

3. Upper boundary

We locate the transition near the right endpoint.

For $N=254$,

$$ f(254) = 36 \lg 254 - 33 - 254 > 0, $$

as computed.

For $N=255$,

$$ f(255) = 36 \lg 255 - 33 - 255 < 0. $$

Thus the function crosses zero between $254$ and $255$, and since $f(x)$ is decreasing for large $x$, all larger integers fail the inequality.

4. Conclusion

We combine the structure:

  • $f(1) < 0$,
  • $f(2) > 0$,
  • $f(x)$ increases up to its unique maximum and then decreases,
  • there is a single crossing point on the right near $N=255$.

Hence the solution set is exactly the integers from $2$ through $254$.

$$ \boxed{2 \le N \le 254.} $$

Program B is slower on average than sequential search precisely for these values of $N$. ∎