In many cases, the relation between encoding space and execution time
translates into combinatorial lower bounds on the computational complexity of
algorithms in the comparison or external memory models. We describe a few cases
which illustrate this relation in a distinct direction, where fast algorithms
inspire compressed encodings or data structures. In particular, we describe the
relation between searching in an ordered array and encoding integers; merging
sets and encoding a sequence of symbols; and sorting and compressing
permutations.