Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence

DOI10.1007/S00026-009-0007-ZzbMATH Open1232.60011arXivmath/0701288OpenAlexW2019666265MaRDI QIDQ659768FDOQ659768

Svante Janson

Publication date: 24 January 2012

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0's, and then evolves by changing each 0 to 1, with then changes done in random order. What is the maximal number of runs of 1's? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order n^{1/2}, and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1; there is also a second order term of order n^{1/3}. We also treat some variations, including priority queues. The proofs use methods originally developed for random graphs.

Full work available at URL: https://arxiv.org/abs/math/0701288

Recommendations

• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence: extended abstract.
• Random time changes for sock-sorting and other stochastic process limit theorems
• Randomized adaptive sorting
• Almost-sure asymptotics for the number of heaps inside a random sequence
• A limit theorem for “quicksort”

zbMATH Keywords

Brownian motionrunspriority queuessorting algorithmevolution of random stringssock-sorting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability: A Graduate Course
• Maximum queue size and hashing with lazy deletion
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• The Distribution Theory of Runs
• The maximum size of a closed epidemic
• Sequence of operations analysis for dynamic data structures
• Orthogonal decompositions and functional limit theorems for random graph statistics
• The maximum of a random walk whose mean path has a maximum
• The analysis of simple list structures
• The complexity of hashing with lazy deletion
• Random walks, Gaussian processes and list structures
• Random time changes for sock-sorting and other stochastic process limit theorems
• A functional limit theorem for random graphs with applications to subgraph count statistics
• Large finite population queueing systems part i: the infinite server model.
• The maximum of a Gaussian process whose mean path has a maximum, with an application to the strength of bundles of fibres
• Brownian motion and a sharply curved boundary
• Title not available (Why is that?)
• Data Structures' Maxima
• Title not available (Why is that?)
• DISTRIBUTION OF GROUPS IN A SEQUENCE OF ALTERNATIVES

Cited In (4)

• Insertion and sorting in a sequence of numbers minimizing the maximum sum of a contiguous subsequence
• The uncover process for random labeled trees
• Title not available (Why is that?)
• Interval graph limits

This page was built for publication: Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence

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