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.

  • 1
    $\begingroup$ 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? $\endgroup$ May 10, 2019 at 19:25

1 Answer 1


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)$.

  • $\begingroup$ 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? $\endgroup$
    – asv
    May 11, 2019 at 13:54
  • $\begingroup$ You can probably prove linearithmic lower bounds in some models even for finite alphabets whose sizes grow with $n$. $\endgroup$ May 11, 2019 at 14:05
  • $\begingroup$ 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 $\endgroup$
    – asv
    May 12, 2019 at 17:03
  • $\begingroup$ Size and cardinality are the same thing. The numbers 1 to $n$ form an alphabet of size $n$. $\endgroup$ May 12, 2019 at 17:28
  • $\begingroup$ Can you give an example of problem with non constant size alphabet? $\endgroup$
    – asv
    May 12, 2019 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.