arXiv Open Access 2015

Counting Inversions Adaptively

Amr Elmasry

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.DS

Penulis (1)

Amr Elmasry

Format Sitasi

APA MLA BibTeX

Elmasry, A. (2015). Counting Inversions Adaptively. https://arxiv.org/abs/1503.01192

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2015
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓