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

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

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