An in-place, subquadratic algorithm for permutation inversion

2019/01/07 by Grzegorz Guśpiel, Guśpiel, Grzegorz · 1 citation
Computer Science · Engineering · #Algorithms and Data Compression #Coding theory and cryptography #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1901.01926

openalex publication_date 2019/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We assume the permutation π is given by an n-element array in which the i-th element denotes the value π(i). Constructing its inverse in-place (i.e. using O(logn) bits of additional memory) can be achieved in linear time with a simple algorithm. Limiting the numbers that can be stored in our array to the range [1...n] still allows a straightforward O(n²) time solution. The time complexity can be improved using randomization, but this only improves the expected, not the pessimistic running time. We present a deterministic algorithm that runs in O(n^3/2) time.

Cited by

• The Structure of In-Place Space-Bounded Computation

Related

• Strictly In-Place Algorithms for Permuting and Inverting Permutations
• Tight Quantum Time-Space Tradeoffs for Permutation Inversion
• In-situ associative permuting
• Counting Inversions Adaptively
• Symmetric QR Algorithm with Permutations