Let's try { reverse( $ a b a a b a a a b ... a^n b ) | n = 0,1,2,... } .
Note that m = n(n+1)/2 + n = O(n^2) Think about adding suffixes to the tree from shortest to longest. So suppose you are now adding something of the form reverse( $ X a^L Y ) where L is the length of the longest run of a's and X and Y are what comes before and after. Well we know the length of Y is at most L and the length of X must be L(L-1)/2+(L-1) = L(L+1)/2 - 1 . What's already in the tree will match no more than 2L characters before a new branch occurs. The new branch will therefore have at least L(L+1)/2 - 1 - 2L characters. This is O(L^2). You should do the math more rigorously, but roughly you will be getting for the total of all branches added, sum_{L=0,1,..n} O(L^2) = O(n^3) = O(m ^ 1.5) with one character per branch. This is super-linear. On Mar 13, 12:47 am, reynald reni <reni.reyn...@gmail.com> wrote: > Construct an infinite family of strings over a fixed alphabet, where > the total length of the edge-labels on their suffix tree grows faster > than O(m), where 'm' is the length of the string. [That is, show that > linear time suffix tree algorithm would be impossible if edge-labels > were written explicitly on the edges.] -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.