Content deleted Content added
m →References: missing rest of page range |
→Analysis: move footnote to avoid confusion as being part of the equation |
||
Line 26:
*some number of comparisons for the binary insertions used to insert the remaining elements.
In the third term, the worst-case number of comparisons for the elements in the first group is two, because each is inserted into a subsequence of <math>S</math> of length at most three. First, <math>y_4</math> is inserted into the three-element subsequence <math>(x_1,x_2,x_3)</math>. Then, <math>y_3</math> is inserted into some permutation of the three-element subsequence <math>(x_1,x_2,y_4)</math>, or in some cases into the two-element subsequence <math>(x_1,x_2)</math>. Similarly, the elements <math>y_6</math> and <math>y_5</math> of the second group are each inserted into a subsequence of length at most seven, using three comparisons. More generally, the worst-case number of comparisons for the elements in the <math>i</math>th group is <math>i+1</math>, because each is inserted into a subsequence of length at most <math>2^{i+1}-1</math>.{{r|fj|c4cs|distrib|knuth}} By summing the number of comparisons used for all the elements and solving the resulting [[recurrence relation]],
this analysis can be used to compute the values of <math>C(n)</math>, giving the formula<ref>{{harvtxt|Knuth|1998}} credits the summation formula to the 1960 Ph.D. thesis of A. Hadian. The approximation formula was already given by {{harvtxt|Ford|Johnson|1959}}.</ref>
:<math>C(n)=\sum_{i=1}^n \left\lceil \log_2 \frac{3i}{4} \right\rceil \approx n\log_2 n - 1.415n</math
or, in [[closed-form expression|closed form]],{{r|gn}}
:<math>C(n)=n\biggl\lceil\log_2\frac{3n}{4}\biggr\rceil-\biggl\lfloor\frac{2^{\lfloor \log_2 6n\rfloor}}{3}\biggr\rfloor+\biggl\lfloor\frac{\log_2 6n}{2}\biggr\rfloor.</math>
| |||