And that will return the array with values of the prefix function.

And we state that this algorithm runs in linear time.

Why is that?

Well, let's first forget for a moment about the inner while loop.

Then what we are left with is initialization which obviously works in

linear time.

And the for loop with linear number of iterations.

And everything inside for loop, but for the while loop, for

which we don't account now, runs in constant time.

So, everything but for the inner while loop works in linear time.

Now on each iteration of the four loop,

the while loop could take in theory as many as linear number of iterations.

And if we sum all that up, that would be quadratic in the length of the pattern.

And now, we will bound the total number of the while loop iterations

by big O of the length of the pattern.

And to do that, we will consider the graph of the values of the prefix function.

Here, the horizontal axis contains positions in the string.

And vertical axis contains values of the prefix function.

The graph always starts in .00.

Because s of 0 is 0.