2026-07-21T11:21:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4729 2024-03-06T10:35:20Z ddc:004 open_access

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting François, Nathanaël Jain, Rahul Magniez, Frédéric Streaming Algorithms Multiple Streams Reversal Sorting We consider unidirectional data streams with restricted access, such as read-only and write-only streams. For read-write streams, we also introduce a new complexity measure called expansion, the ratio between the space used on the stream and the input size. We give tight bounds for the complexity of reversing a stream of length n in several of the possible models. In the read-only and write-only model, we show that p-pass algorithms need memory space Theta(n/p). But if either the output stream or the input stream is read-write, then the complexity falls to Theta(n/p^2). It becomes polylog(n) if p = O(log n) and both streams are read-write. We also study the complexity of sorting a stream and give two algorithms with small expansion. Our main sorting algorithm is randomized and has O(1) expansion, O(log n) passes and O(log n) memory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathanaël François and Rahul Jain and Frédéric Magniez 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.654 urn:nbn:de:0030-drops-47298 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.654 eng https://creativecommons.org/licenses/by/3.0/legalcode