On bounding the average cost of top-down merge sort - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T09:49:06Z http://mathoverflow.net/feeds/question/105328 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105328/on-bounding-the-average-cost-of-top-down-merge-sort On bounding the average cost of top-down merge sort Christian 2012-08-23T15:14:40Z 2012-08-24T22:25:44Z <p>Let $A_n$ be the average number of comparisons to sort $n$ keys by merging them in a top-down fashion (see any algorithm textbook). It can he shown that $$A_0 = A_1 = 0;\quad A_n = A_{\lfloor{n/2}\rfloor} + A_{\lceil{n/2}\rceil} + n - \frac{\lfloor{n/2}\rfloor}{\lceil{n/2}\rceil+1} - \frac{\lceil{n/2}\rceil}{\lfloor{n/2}\rfloor+1}.$$ (See Knuth's AOCP, for instance.) Flajolet and Golin in 1993 used complex analysis (Mellin transforms) and Fourier analysis to find a precise asymptotic approximation of $A_n$. I am interested in finding lower and upper bounds on $A_n$ of the form $n\lg n + \alpha n + \beta$, where $\lg n$ is the binary logarithm, <em>not</em> using these powerful but complicated analytical approaches.</p> <p>By distinguishing on the parity of $n$, we simply get $$A_{2p} = 2 A_{p} + 2p - 2 + \frac{2}{p+1};\quad A_{2p+1} = A_{p} + A_{p+1} + 2p - 1 + \frac{2}{p+2}.$$ I tried difference equations, by letting $\Delta_n := A_{n+1} - A_{n}$, yielding $$\Delta_{2p} = \Delta_{p} + 1 + \frac{2}{p+2} - \frac{2}{p+1};\quad \Delta_{2p+1} = \Delta_p + 1.$$ Then, I am stuck.</p> <p>The same study for the maximum number of comparisons leads to simpler difference equations: $\Delta_{2p} = \Delta_{2p+1} = \Delta_{p} + 1$, which implies $\Delta_n = \lfloor{\lg n}\rfloor + 1$, to wit, the number of bits in the binary expansion of $n$. From there, a closed form for the maximum cost $\sum_{k=1}^{n-1}\Delta_k$ follows relatively easily (see Flajolet and Sedgewick, for instance).</p> <p>Any idea how to bound $\Delta_k$ and $\sum_{k=1}^{n-1}\Delta_k$ in the present case?</p> http://mathoverflow.net/questions/105328/on-bounding-the-average-cost-of-top-down-merge-sort/105361#105361 Answer by Douglas Zare for On bounding the average cost of top-down merge sort Douglas Zare 2012-08-23T23:10:36Z 2012-08-23T23:10:36Z <p>Inductively, if $A_p \le p \log_2 p + \alpha p + \beta$, then </p> <p>$A_{2p} \le ((2p) \log_2 (2p) + \alpha (2p) + \beta) + (\beta -2 + \frac {2}{p+1})$</p> <p>so we'll want $\beta-2 + \frac{2}{p+1} \le 0.$</p> <p>The odd case is a little harder. Assume the inequality is true for $A_p,A_{p+1}.$</p> <p>$A_{2p+1} = A_p + A_{p+1} + 2p - 1 + \frac{2}{p+2}$</p> <p>$\le (p+1)\log_2 (p+1) + p ~\log_2 p + \alpha(2p+1) + \beta + \beta + 2p - 1 + \frac{2}{p+2}.$</p> <p>Using $\log_2 x \le \frac{(x-(p+1/2))}{(p+1/2)\log 2} + \log_2 (p+1/2)$ at $x=p, p+1$:</p> <p>$$A_{2p+1} \le (p+1)\log_2 (p+1/2) + p~\log_2p + \frac{p+1}{(2p+1)\log 2} - \frac {p}{(2p+1)\log 2} \\ + \alpha(2p+1) + \beta + \beta + 2p - 1 + \frac{2}{p+2}$$</p> <p>$$A_{2p+1} \le \bigg((2p+1)\log_2(2p+1) + \alpha(2p+1) + \beta \bigg) + \\ \beta -2+ \frac{2}{p+2}+\frac{1}{(2p+1)\log 2}.$$</p> <p>So, we'll also want $\beta - 2 + \frac{2}{p+2} + \frac{1}{(2p+1)\log 2} \le 0.$ Then if we choose $\alpha, \beta$ so that the base of the induction is satisfied, we get $A_n \le n \log_2 n + \alpha n + \beta.$</p> <p>I think that you can get slightly better bounds by starting the induction higher, but let's start it at $p=1, A_2 = 1, A_3 = \frac 8 3.$ Then we want $4$ inequalities to be satisfied: </p> <p>$1 \le 2 \log_2 2 + 2\alpha + \beta$ </p> <p>$\frac 8 3 \le 3 \log_2 3 + 3\alpha + \beta$</p> <p>$\beta -2 + 1 \le 0$</p> <p>$\beta -2 + \frac 23 + \frac{1}{3 \log 2} \le 0$</p> <p>and we want to minimize $\alpha$ and then minimize $\beta$ for that $\alpha$ subject to these constraints. If I calculate correctly, then the solution is $\alpha = -\frac76 + \frac{1}{6 \log 2} = -0.9263, \beta = \frac43 - \frac 1{3\log 2} = 0.8524,$ and $A_n \le n \log_2 n + \alpha n + \beta$ should be satisfied for all $n \ge 2$. You can get a slightly lower value of $\alpha$ if you don't need the formula to work for $n=2$.</p> http://mathoverflow.net/questions/105328/on-bounding-the-average-cost-of-top-down-merge-sort/105417#105417 Answer by Christian for On bounding the average cost of top-down merge sort Christian 2012-08-24T20:02:26Z 2012-08-24T20:02:26Z <p>Douglas,</p> <p>Thank you very much for this elegant and didactic derivation. This is what I was hoping for.</p> <p>I just have a few remarks.</p> <p>The inequality on $\beta$ obtained from bounding $A_{2p+1}$ always implies the inequality obtained from $A_{2p}$, so we can get rid of the latter; in particular, we don't need the third inequality when setting $p=1$ at the end. </p> <p>When $p=1$, the two first inequalities show that if we want to minimize $\alpha$, we can maximize $\beta \geq 0$, and we know the upper bound on $\beta$ to be the value you provide. Then, the <em>second</em> inequality (again the odd case) yields the lowest value for $\alpha$, that is, $\alpha = \frac{4}{9} - \lg 3 + \frac{1}{9\ln 2} \simeq -0.9802$.</p> <p>The advanced analytical techniques I alluded to yield $A_n = n\lg n - (1.25 \pm 0.01)n + O(1)$.</p> <p>I will work out the lower bound following your inductive method. Thanks again!</p> http://mathoverflow.net/questions/105328/on-bounding-the-average-cost-of-top-down-merge-sort/105429#105429 Answer by Christian for On bounding the average cost of top-down merge sort Christian 2012-08-24T22:25:44Z 2012-08-24T22:25:44Z <p>[I can't edit my answer.] Douglas is right, of course: when you have two lower bounds, you can only take the largest, so the <em>even</em> case rules for deciding $\alpha$, which is indeed the value given by Douglas. Sorry about that.</p> <p>Perhaps a better upper bound on $\lg p$ and $\lg(p+1)$ in terms of $\lg(2p+1)$ would yield a better result?</p>