Observe that in the general case this algorithm is \(O(Nm\log(K))\) where \(N\) is the length of the dataset, \(m\) is the average length of a prefix match, and \(K\) is the number of splits. It is therefore incorrect to call this algorithm linear time in the general case, for ours it is. Because the length of the longest match is bounded above by the length of the longest sequence, as long as the size of the dataset is independent of the length of the longest sequence in the dataset, this algorithm remains efficient.