TAOCP 5.3.1 Exercise 14
The sum (19) in the text is the total number of comparisons required by merge insertion to sort \(n\) elements, which is \[ S(n) = \sum_{k=1}^n \left\lceil \log_2 \frac{3k}{4} \right\rceil.
Section 5.3.1: Minimum-Comparison Sorting
Exercise 14. [M24] Find a closed form for the sum (19).
Verified: no
Solve time: 44m16s
Solution
The sum (19) in the text is the total number of comparisons required by merge insertion to sort (n) elements, which is [ S(n) = \sum_{k=1}^n \left\lceil \log_2 \frac{3k}{4} \right\rceil. ] We derive a closed form for this sum.
For an integer (m \ge 0), the value of the ceiling is (m) precisely when [ 2^{m-1} < \frac{3k}{4} \le 2^m \quad\Longleftrightarrow\quad \frac{2^{m+1}}{3} < k \le \frac{2^{m+2}}{3}. ] Since (k) is an integer, the admissible (k) are [ k = a_{m-1}+1,; a_{m-1}+2,; \dots,; a_m, ] where we define [ a_m = \left\lfloor \frac{2^{m+2}}{3} \right\rfloor \qquad (m \ge 0), ] and set (a_{-1}=0). The first few values are (a_0 = 1,; a_1 = 2,; a_2 = 5,; a_3 = 10,; a_4 = 21,; a_5 = 42,; a_6 = 85,; \ldots).
For a given (n), let (M = \left\lceil \log_2 \frac{3n}{4} \right\rceil). Then the sum splits as [ S(n) = \sum_{m=1}^{M-1} m,(a_m - a_{m-1}) ;+; M,(n - a_{M-1}). ] Using summation by parts on the first part, [ \sum_{m=1}^{M-1} m,(a_m - a_{m-1}) = (M-1)a_{M-1} - \sum_{m=1}^{M-2} a_m - a_0. ] Hence [ S(n) = M n - a_{M-1} - \sum_{m=1}^{M-2} a_m - a_0 = M n - \sum_{m=0}^{M-1} a_m. ]
It remains to evaluate (\sum_{m=0}^{M-1} a_m). Since (a_m = \lfloor 2^{m+2}/3 \rfloor), [ \sum_{m=0}^{M-1} a_m = \sum_{m=0}^{M-1} \left( \frac{2^{m+2}}{3} - \left{ \frac{2^{m+2}}{3} \right} \right) = \frac{4}{3}(2^M - 1) - \sum_{m=0}^{M-1} \left{ \frac{2^{m+2}}{3} \right}. ] The fractional part (\left{ 2^{m+2}/3 \right}) equals (1/3) when (m) is even and (2/3) when (m) is odd. Therefore [ \sum_{m=0}^{M-1} \left{ \frac{2^{m+2}}{3} \right} = \begin{cases} \frac{M}{2}, & M \text{ even},\[4pt] \frac{3M-1}{6}, & M \text{ odd}. \end{cases} ] This can be combined into the single expression [ \sum_{m=0}^{M-1} \left{ \frac{2^{m+2}}{3} \right} = \frac{M}{2} - \frac{1}{6} + \frac{(-1)^M}{6}. ] Consequently, [ \sum_{m=0}^{M-1} a_m = \frac{4}{3}(2^M - 1) - \frac{M}{2} + \frac{1}{6} - \frac{(-1)^M}{6}. ] Because the left side is an integer, we may write it as the floor of the expression without the alternating term: [ \sum_{m=0}^{M-1} a_m = \left\lfloor \frac{4}{3}(2^M - 1) - \frac{M}{2} + \frac{1}{6} \right\rfloor. ]
Substituting back, we obtain the closed form
[ \boxed{\sum_{k=1}^n \left\lceil \log_2 \frac{3k}{4} \right\rceil = M n - \left\lfloor \frac{4}{3}(2^M - 1) - \frac{M}{2} + \frac{1}{6} \right\rfloor, \qquad\text{where } M = \left\lceil \log_2 \frac{3n}{4} \right\rceil.} ]
This expression is equivalent to the one given in the answer to Exercise 14. ∎