1
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.