Back to search

University of Waterloo

Inverting Permutations In Place

Abstract

dc:description.abstract

We address the problem of quickly inverting the standard representation of a permutation on $n$ elements in place. First, we present a naive algorithm to do it using $O(\log n)$ extra bits in O(n2) time in the worst case. We then improve that algorithm, using a small bit vector, to use $O(\sqrt n)$ extra bits in $O(n \sqrt n)$ time. Using a different approach, we present an algorithm to do it using $O(\sqrt n \log n)$ extra bits in $O(n \log n)$ time. Finally, for our main result, we present a technique that leads to an algorithm to invert the standard representation of a permutation using only O(\log2 n) extra bits of space in $O(n \log n)$ time in the worst case.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Robertson, Matthew

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/9535

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Robertson, Matthew. Inverting Permutations In Place. University of Waterloo, 2015. http://hdl.handle.net/10012/9535