Given a k-character query string and an array of n strings arranged in lexicographical order, computing the rank of the query string among the n strings or deciding whether it occurs in the array requires the inspection of $$ \Theta\left( \frac {k\log {\log n}} {\log {\log {(4+\frac{k \log{\log n}}{\log n})}}}+k+\log n\right) $$ characters in the worst case.

Adaptivity in sorting algorithms is sometimes gained at the expense of practicality. We give experimental results showing that Splaysort — sorting by repeated insertion into a Splay tree — is a surprisingly efficient method for in-memory sorting. Splaysort appears to be adaptive with respect to all accepted measures of presortedness, and it outperforms Quicksort for sequences with modest amounts of existing order. Although Splaysort has a linear space overhead, there are many applications for which this is reasonable. In these situations Splaysort is an attractive alternative to traditional comparison-based sorting algorithms such as Heapsort, Mergesort, and Quicksort.

We show that given a k-character query string and an ai-ray of n strings arranged in alphabetical order, finding a matching string or report that no such string exists requires a ( k log log n +k+logn log log (4+ k 1;:;; n ) )character comparisons in the worst case, which is tight.

Article Free Access Share on The complexity of searching a sorted array of strings Authors: Arne Andersson Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden Department of Computer Science, Lund University, Box 118, 22100 Lund, SwedenView Profile , Torben Hagerup Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, Germany Max-Planck-Institut für Informatik, Im Stadtwald, D-66123 Saarbrücken, GermanyView Profile , Johan Håstad Department of Computer Science, Royal Institute of Technology, 10044 Stockholm, Sweden Department of Computer Science, Royal Institute of Technology, 10044 Stockholm, SwedenView Profile , Ola Petersson Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden and Department of Mathematics, Statistics and Computer Science, Växjö University, 35195 Växjö, Sweden Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden and Department of Mathematics, Statistics and Computer Science, Växjö University, 35195 Växjö, SwedenView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 317–325https://doi.org/10.1145/195058.195175Published:23 May 1994Publication History 6citation285DownloadsMetricsTotal Citations6Total Downloads285Last 12 Months16Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF