PhD Seminar • Algorithms and Complexity: Raising Permutations to Powers in Place

Hicham El-Zein, PhD candidate
David R. Cheriton School of Computer Science

Given a permutation of $n$ elements, stored as an array, we address the problem of replacing the permutation by its $k^{\mathrm{th}}$ power. We aim to perform this operation quickly using $o(n)$ bits of extra storage. To this end, we first present an algorithm for inverting permutations that uses $O(\lg^2 n)$ additional bits and runs in $O(n\lg n)$ worst case time. This result is then generalized to the situation in which the permutation is to be replaced by its $k^{\mathrm{th}}$ power.

An algorithm whose worst case running time is $O(n\lg n)$ and uses $O(\lg^2 n + \min\{k\lg n,n^{\rfrac{3}{4}+\epsilon}\})$ additional bits is presented.