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.
$\begingroup$
$\endgroup$
1
-
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 FilmusMay 10, 2019 at 19:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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)$.
answered May 10, 2019 at 19:27
-
$\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$– asvMay 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$– asvMay 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$– asvMay 12, 2019 at 18:04