Home.... | log in.... | Pub my question! | Sign-up....
Java-index >> Other Topics >> Algorithms

Time complexity of suffix tree

Hi,Not sure about the time complexity of naive alogorithm. What is the best, avg, worst case? When will each happen?
[130 byte] By [hiJavaa] at [2007-10-1 16:32:46]
«« Getting the ip of the user
»» JSP and HashMap
# 1
We don't have your text book, so you'll need to fill us in on exactly what the "naive" suffix tree algortihm is.
RadcliffePikea at 2007-7-11 0:51:36 > top of Java-index,Other Topics,Algorithms...
# 2

Hi,

In my text book, it shows

for i = 1 to N - M + 1 do

if s(i|M) == p then FOUND

Time complexity is O(MN).

I think that is the naive algorithm.

However, for the assignment I am supposed to do, the test data are files with lots of "A" and another 1 with random "ACGT". So how these affects the time complexity?

hiJavaa at 2007-7-11 0:51:36 > top of Java-index,Other Topics,Algorithms...
Other Topics
Algorithms

Other Topics New Topic

Other Topics Hot Topic

Other Topics

All Classified