12 - Ranking suffixes

Summary

Introduction

The idea of ranking the elements of a list crops up frequently. An element x is assigned rank r if there are exactly r elements of the list less than x. For example, rank [51, 38, 29, 51, 63, 38] = [3, 1, 0, 3, 5, 1]. This scheme ranks from 0 and from lowest to highest, but one can also rank from 1 and from highest to lowest, as when ranking candidates by their marks in an examination. Rankings are distinct if and only if the list does not contain duplicates, in which case rank xs is a permutation of [0 .. length xs − 1].

In this pearl we consider the problem of ranking the suffixes of a list rather than the list itself. It takes Θ(n log n) steps to rank a list of length n, assuming a test x < y takes constant time. Since in the worst case it takes Θ(n) such tests to make one lexicographic comparison between two suffixes of a list of length n, it seems that ranking the suffixes of a list should require Θ(n² log n) basic comparisons. The point of this pearl is to show that only Θ(n log n) steps are necessary. Asymptotically speaking, it takes no more time to rank the suffixes of a list than it does to rank the list itself. Surprising but true.