Временная сложность создания Суффиксного дерева

Для создания суффиксного дерева в худшем корпусе, если бы вся буква последовательности отличается, сложность была бы чем-то как

n + (n-1) + (n-2) ... 1 = n*(n+1)/2

, который является O (n^2).

Однако согласно http://en.wikipedia.org/wiki/Suffix_tree здание суффиксное дерево берет O (n) время. Что я пропускаю здесь?