An Improved Lower Bound for Stack Sorting

arXiv1212.0836MaRDI QIDQ6237733FDOQ6237733

Authors: Luke Schaeffer 

Publication date: 4 December 2012

Abstract: We consider the problem of sorting elements on a series of stacks, introduced by Tarjan and Knuth. We improve the asymptotic lower bound for the number of stacks necessary to sort $n$ elements to $0.561lo{g}_{2}n+O(1)$. This is the first significant improvement since the previous lower bound, $1/2lo{g}_{2}n+O(1)$, was established by Knuth in 1972.

Mathematics Subject Classification ID

Asymptotic enumeration (05A16)

This page was built for publication: An Improved Lower Bound for Stack Sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237733)