Amr Elmasry

Memory-Adjustable Navigation Piles with Applications to Sorting and Convex Hulls

2021 · ACM Transactions on Algorithms

We consider space-bounded computations on a random-access machine, where the input is given on a read-only random-access medium, the output is to be produced to a write-only sequential-access medium, and the available workspace allows random …

Counting Inversions Adaptively

2015 · arXiv (Cornell University)

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 …