Counting Inversions Adaptively
classification
💻 cs.DS
keywords
inversionsadaptivelyalgorithmcountingcomputationefficientgiveintegers
read the original abstract
We give a simple and efficient algorithm for adaptively counting inversions in a sequence of $n$ integers. Our algorithm runs in $O(n + n \sqrt{\lg{(Inv/n)}})$ time in the word-RAM model of computation, where $Inv$ is the number of inversions.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.