New answers tagged complexity
The algorithm you are looking for is Ukkonen's suffix tree. It runs in O(n). The algorithm you describe is not O(n log n). It has that number of string comparisons. In the extreme case, where your string being is "verylong_verylong_", comparisons take O(n), bringing your algorithm down to quadratic complexity.
Big O time complexity of divide and conquer algorithms is not affected by what fraction you divide things into. This is because logs of different bases differ by only a constant factor. So the Big O time complexity in your case is the same as if you separate 50% out. So you should get the usual nLogn sort.
What approach should I adopt to produce a useful GUI map of this application? How do people manage such things in a time efficient way? Quick Short Answer State Transitions Charts are a good idea. Represent each different screen as a single transition, very general, not too much detail, first. Add detail later. Long Boring Extended Answer ...
While the end result is correct, I wouldn't accept what is written in the question as an answer, because I can't really see how it gets to the answer. The innermost loop: There are two cases. If j % i ≠ 0 then it iterates once, if j % i = 0 then it iterates j times. The middle loop: Given i, it iterates i^2 times. The value of j will range from 1 to i^2. ...
Top 50 recent answers are included