# Non consant size alphabet

Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.

• The question seems to be missing some context. Can you give an example where you saw that an algorithm worked on a constant size alphabet? – Yuval Filmus May 10 '19 at 19:25

The classical example is sorting. For any constant-size alphabet, you can sort a string of length $$n$$ in time $$O(n)$$. However, for unbounded alphabets, the best you can do (under the comparison model, as well as some of its generalizations) is $$\Theta(n\log n)$$.
• You can probably prove linearithmic lower bounds in some models even for finite alphabets whose sizes grow with $n$. – Yuval Filmus May 11 '19 at 14:05
• Size and cardinality are the same thing. The numbers 1 to $n$ form an alphabet of size $n$. – Yuval Filmus May 12 '19 at 17:28