file.pdf (59.77 kB)
Download file

Counting Inversions in Lists

Download (59.77 kB)
journal contribution
posted on 01.03.2005, 00:00 authored by Anupam Gupta, Francis X. Zane
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.

History

Publisher Statement

(c) 2005 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.

Date

01/03/2005

Usage metrics

Exports