# Suffix Tree algorithm complexity [closed]

I really get confused by all the different complexities you find around. One is $O(n \log n)$, the next $O(n \cdot |\Sigma|)$. Personally I think it's the last one, but I'm really not that confident with it to say so. Well on average we go $\log n$ deep and need at max $|\Sigma|$ steps to find a corresponding node that matches (or not). Thus I would come up with $O(n \cdot |\Sigma| \cdot \log n)$.

Repeat the following for all suffixes of the given string, right to left.

1. Scan if its in tree
• Not in tree -> add it as new node
• Is partly in tree -> fork here, such that the matching part remains
2. Go back to step 1 until the sequence that was observed equals the source

There are also multiple different models. Some algorithms are designed for the regime where $\Sigma=\{0,1\}$ or where you have a small finite-sized alphabet (e.g., $|\Sigma|=256$), where it is reasonable to consider $|\Sigma| \in O(1)$. Consequently, the running time for those algorithms might not include any dependence on $|\Sigma|$ -- which is reasonable if you assume that $|\Sigma| \in O(1)$. Other algorithms are designed to work even when the size of the alphabet is large. For those, the dependence on $|\Sigma|$ is at the heart of the problem. Therefore, you'll also find some algorithms designed for the large-alphabet regime, and typically the running times that are quoted for those algorithms do show the dependence on $|\Sigma|$. Therefore, when you read a paper on a suffix tree algorithm, if you want to use the algorithm on a situation where the alphabet size is large, you need to carefully examine the assumptions that were made during the running time analysis. Does the quoted running time include the dependence on $|\Sigma|$? Does the paper assume $|\Sigma| \in O(1)$?
Finally, the dependence on $|\Sigma|$ can depend on subtle aspects of how the data structures are instantiated. Therefore, a high-level description of the algorithm is often not enough -- you often need to know how the tree is represented and how the individual steps are instantiated to tell what the dependence on $|\Sigma|$ will be.