A naive implementation of this algorithm requires O(n 2 ) invocations of local classifiers, where n is the number of the words in the sentence, because we need to update the probabilities over the words at each iteration.
a k-th order Markov assumption obviously allows us to skip most of the probability updates, resulting in O(kn) invocations of local classifiers.