Non consant size alphabet
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)$.