Nested loop running time

Running time of nested loop

Given the following pattern matching algorithm which decides whether there is an occurrence of a pattern of size (m) in a text of size (n). The algorithm compares the pattern in a given location in the text checking all characters from left to right.

(1) Assuming (m) is much smaller than (n) prove that the above algorithm has a best run time of O(n) in case the pattern is not found in the text (2) Show that finding the pattern “a” in the text “abcdefg” takes O(1) operations (3) Prove that the algorithm has a worst run time of O(n^2)

Nested loop time complexity

The algorithm has two nested loops. The outer loop runs (n – m + 1) times while the inner loop runs (m) times. For large values of (n) and small values of (m) the outer loop will run (n) times while the inner loop will run few times. This is almost the same as having a single outer loop that runs (n) times. So the running time for this algorithm is O(n) if (m) is way smaller than (n). Finding the pattern “a” in “abcdefg” is obviously O(1) simply because the loops never run in full. The match is found from the very first iteration. Notice that in worst case the algorithm will run the two nested loops in full. In other words it will run (n – m + 1) x m times. For large values of (n) and (m) for example if m = n/2 then this expression becomes (n/2 + 1) * (n/2) and for large values of (n) this is effectively (n^2).

Thanks for reading. Please use the comments section below for feedback.

Tags:
2 Comments

Add a Comment

Your email address will not be published. Required fields are marked *