# How does the runtime of the Ukkonen's algorithm depend on the alphabet size?

I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time.

Here is a citation from the book "Algorithms on strings, trees and sequences" by Dan Gusfield (section 6.5.1):

"... the Aho-Corasick, Weiner, Ukkonen and McCreight algorithms all either require $\Theta(m|\Sigma|)$ space, or the $O(m)$ time bound should be replaced with the minimum of $O(m \log m)$ and $O(m \log|\Sigma|)$".

[$m$ is the string length and $\Sigma$ is the size of the alphabet]

I don't understand why that is true.

• Space: well, in case we represent branches out of the nodes using arrays of size $\Theta(|\Sigma|)$, then, indeed, we end up with $\Theta(m|\Sigma|)$ space usage. However, as far as I can see, it is also possible to store the branches using hash tables (say, dictionaries in Python). We would then have only $\Theta(m)$ pointers stored in all hash tables altogether (since there are $\Theta(m)$ edges in the tree), while still being able to access the children nodes in $O(1)$ time, as fast as when using arrays.
• Time: as mentioned above, using hash tables allows us to access the outgoing branches of any node in $O(1)$ time. Since the Ukkonen's algorithm requires $O(m)$ operations (including accessing children nodes), the overall running time then would be also $O(m)$.

I would be very grateful to you for any hints on why I am wrong in my conclusions and why Gusfield is right about the dependence of the Ukkonen's algorithm on the alphabet.

• I don't think there is any proof to the effect that an alphabet-size independent time/space bound is impossible. I believe Gusfield made the statement because there is no known method to get rid of the time bound completely. In order to establish one, you'd have to elaborate on your hash functions in more detail. A true worst-case O(1) time bound for hash lookup requires a perfect hash. It's not clear to me how to do this during the algorithm (because the hash entries aren't static at that point). – jogojapan Mar 7 '13 at 5:06
• (cont'd) You could do it once the tree is complete, but then the time bound for the algorithm itself would still be unchanged. (+1 for the question though.) – jogojapan Mar 7 '13 at 5:06
• Useful context: Ukkonen's algorithm explained – FrankW May 7 '14 at 14:22

As @jogojapan mentions in the comments, hasing generally is only amortized $O(1)$, so you would only get amortized bounds for the algorithm. However, I think you do not even get these: In order to get amortized $O(1)$ hashing, the hash tables have to be of size $\Omega(\Sigma)$, so you still have $\Theta(m\Sigma)$ space (and the same time requirement for initialization).