0
$\begingroup$

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
$\endgroup$

closed as unclear what you're asking by D.W., Luke Mathieson, Juho, Cornelius Brand, user340082710 Apr 17 '15 at 20:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

4
$\begingroup$

There is no one complexity for all suffix tree algorithms. There are multiple algorithms, with different running times. It is not helpful to talk about this as though there was only one complexity that applies to all algorithms for computing a suffix tree. If you want to ask what is the running time of an algorithm for this task, you need to specify which algorithm you are asking about.

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.

I suggest you read What are the effects of the alphabet size on construct algorithms for suffix trees?

I also suggest you take a look at What is the difference between an algorithm, a language and a problem?, to help you think clearly about the difference between a problem vs an algorithm.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.