The value of $r$, with $r≤ b$, that minimizes the expression $(b/r)(n+2^r)$ in the analysis of the radix-sort algorithm

Question

In chapter 8 of the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, lemma 8.4 is proved. (my question is after the proof of the lemma)

Given $n$ $b$-bit numbers and any positive integer $r≤b$, RADIX-SORT correctly sorts these numbers in $Θ((b/r)(n+2^r))$ time if the stable sort it uses takes $Θ(n+k)$ time for inputs in the range $0$ to $k$.

Proof:

For a value $r≤b$, we view each key as having $d=⌈b/r⌉$ digits of $r$ bits each. Each digit is an integer in the range $0$ to $2^r-1$, so that we can use counting sort with $k = 2^r-1$. (For example, we can view a 32-bit word as having four 8-bit digits, so that $b = 32$, $r=8$, $k = 2^r-1 = 255$, and $d = b/r = 4$.) Each pass of counting sort takes time $Θ(n+k)=Θ(n+2^r)$ and there are $d$ passes, for a total running time of $Θ(d(n+2^r))= Θ((b/r)(n+2^r)).$

goes on... and in this part I will ask my question. In the quote I will mark the points of the question.

For given values of $n$ and $b$, we wish to choose the value of $r$, with $r ≤ b$, that minimizes the expression $(b/r)(n+2^r)$. If $b < ⌊\lg n⌋$ (question : what is the motivation that led to the choice of this inequality?), then for any value of $r \leq b$, we have that $(n+2^r)=Θ(n)$. Thus, choosing $r = b$ yields a running time of $(b/b)(n+2^r)=Θ(n)$, which is asymptotically optimal. If $b \geq ⌊\lg n⌋$, then choosing $r= ⌊\lg n⌋$ gives the best time to within a constant factor, which we can see as follows. Choosing $r = ⌊\lg n⌋$ nc yields a running time of $Θ(bn(\lg n)$. As we increase $r$ above $⌊\lg n⌋$, the $2^r$ term in the numerator increases faster than the $r$ term in the denominator, and so increasing $r$ above $⌊\lg n⌋$ yields a running time of $Ω(bn/\lg n)$. If instead we were to decrease $r$ below $⌊\lg n⌋$, then the $b/r$ term increases and the $n+2^r$ term remains at $\Theta(n)$.

Answer 1

For fixed $n$, let $f(r)=(b/r)(n+2^r)$ where $r>0$.

Since $f(r)>(b/r)n$, $\ f(0^+)=\infty$.
Since $f(r)>(b/r)2^r$, $\ f(\infty)=\infty.$ Hence there exists $m$ such that $f(r)$ reaches its global minimum at $r=m$. By the extreme value theorem, we have $$f'(m)=0,$$ which means $-\frac b{m^2}(n+2^m)+\frac bm(2^m\log_e2)=0$. $$n=2^m(m\log_e2-1).$$

---

What we are interested in is what happens when $n$ goes to infinity. So we consider $m$ as a function of $n$ that is determined by the equation above.

As $n$ goes to infinity, we see that $m$ must go to infinity as well. Taking $\log_2(\cdot)$ of both sides, we get $$\log_2n=m +\log_2(m\log_e2-1).$$ Since $\lim_{m\to\infty}\frac{\log_2(m\log_e2-1)}{m}=0$, we see that $$\lim_{n\to\infty}\frac{m}{\log_2n}=1$$

Recall that $f(r)$ takes the minimum value at $r=m$ for a fixed $n$. That is why the book checks the value of $f(r)$ at or near the point $r=\log_2n$.