Theoretical Computer Science

Organizers: Paweł Idziak
Usual time and place: Wednesday, 16:15-18:00, room 1094
event-date: 13.04.2011
Speaker: Grzegorz Guśpiel
Title of the talk: A Constant Space, Subquadratic Algorithm for Inverse Permutation
Abstract: We assume the permutation is given by an array in which the i-th element denotes the value at i. Finding its inverse can be achieved in linear time with a simple cycle-based algorithm. Limiting the numbers that can be stored in our array to the range of the permutation still allows a simple O(n2) solution. A better O(n3/2) algorithm will be presented.