0
$\begingroup$

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.

$\endgroup$
  • 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$ – Yuval Filmus May 10 '19 at 19:25
2
$\begingroup$

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

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