# 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? May 10, 2019 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)$$.

• For unbounded you mean infinity, i. e. the alphabet is not a set of finite letters but for example the set of all natural numbers, right?
– asv
May 11, 2019 at 13:54
• You can probably prove linearithmic lower bounds in some models even for finite alphabets whose sizes grow with $n$. May 11, 2019 at 14:05
• What means finite alphabets whose sizes grow with n? Sorry but I am misunderstanding something. Size and cardinality of a set are the same? Can you give an example with non constant size alphabet? Usaually I think an alphabet with fine elemnts such as A,C,T,G, alphabet of DNA. Thanks
– asv
May 12, 2019 at 17:03
• Size and cardinality are the same thing. The numbers 1 to $n$ form an alphabet of size $n$. May 12, 2019 at 17:28
• Can you give an example of problem with non constant size alphabet?
– asv
May 12, 2019 at 18:04