Ukkonen-s-Suffix-Tree-Algorithm icon indicating copy to clipboard operation
Ukkonen-s-Suffix-Tree-Algorithm copied to clipboard

O(n^2) time complexity due to list copy

Open IgSaf opened this issue 4 years ago • 0 comments

There is a copy of list in unfold function. It leads to O(len(remains)) time complexity for this operation. And due to being inside while remainder > 0 this gains O(n^2) time complexity for the whole implementation (e.g. for "aaaaab").

IgSaf avatar Jan 06 '21 10:01 IgSaf