Design and Analysis of Algorithms

Time-Space Trade-off 449

Let us end this discussion by analysing the time taken by this part of the KMP algorithm. The outer loop

executes m times. Each iteration of the inner loop decreases the value of the formula

overlap[i+1], and

this formula’s value only increases by one when we move from one iteration of the outer loop to the next.

Since the number of decreases is at most the number of increases, the inner loop also has at most m iterations,

and the total time for the algorithm is O(m).

The entire KMP algorithm consists of this overlap computation, followed by the main part of the

algorithm in which we scan the text, using the overlap values ...