  We characterize the complexity functions of subshifts up to asymptotic
equivalence. The complexity function of every aperiodic function is
non-decreasing, submultiplicative and grows at least linearly. We prove that
conversely, every function satisfying these conditions is asymptotically
equivalent to the complexity function of a recurrent subshift, equivalently, a
recurrent infinite word. Our construction is explicit, algorithmic in nature
and is philosophically based on constructing certain 'Cantor sets of integers',
whose 'gaps' correspond to blocks of zeros. We also prove that every
non-decreasing submultiplicative function is asymptotically equivalent, up a
linear error term, to the complexity function of a minimal subshift.
