His Algorithm D takes an uncompressed[2] trie for S [ k + 1.. n ] {\displaystyle S[k+1..n]} and extends it into a trie for S [ k . . n ] {\displaystyle S[k..n]} . This way, starting from the trivial trie for S [ n . . n ] {\displaystyle S[n..n]} , a trie for S [ 1.. n ] {\displaystyle S[1..n]} can be built by n − 1 {\displaystyle n-1} successive calls to Algorithm D; however, the overall run time is O ( n 2 ) {\displaystyle O(n^{2})} .