Counting inversions in lists

Anupam Gupta, Francis X. Zane

Research output: Contribution to conferencePaperpeer-review


In a recent paper, Ajtai et al. [1] give a streaming algorithm to count the number of inversions in a stream L ∈ [m]n using two passes and O(ε-1 √n log n(log m + log n)) space. Here, we present a simple randomized streaming algorithm for the same problem that uses one pass and O(ε-3 log2 n log m) space. Our algorithm is based on estimating quantiles of the items already seen in the stream, and using that to estimate the number of inversions involving each element.

Original languageEnglish (US)
Number of pages2
StatePublished - 2003
EventConfiguralble Computing: Technology and Applications - Boston, MA, United States
Duration: Nov 2 1998Nov 3 1998


OtherConfiguralble Computing: Technology and Applications
Country/TerritoryUnited States
CityBoston, MA

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Counting inversions in lists'. Together they form a unique fingerprint.

Cite this