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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
//Includes #include <iostream> //STD using namespace std; //Receives input text, pattern and their sizes int PatternMatch (char* text, char* pat, int n, int m) { //Go through the text character by character for (int i = 0; i <= n - m; i++) { //For each position (i) of the text //go through the pattern character //by character then compare int j = 0; while (j < m && pat[j] == text[i + j]) { j++; } //If all comparisons succeeded then //the pattern was found if(j == m) return 1; } //No match return 0; } //Main function void main() { //Sample strings char text[] = "abcdefg"; char pat[] = "fg"; //Check pattern if (PatternMatch(text, pat, 7, 2)) { cout << "Pattern found" << endl; } else { cout << "Pattern not found" << endl; } } |
(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.
what do you think the following solution? Same efficiency?
int patternMatch(char *text, char *pat, int n, int m)
{
int i, j = 0;
if (n < m) return 0; for (i = 0; i < n; i++) { if (text[i] == pat[j]) { j++; if (j == m) return 1; continue; } j = 0; } return 0; }
I am a QA Engineer and the best way to test software or code is to try it. Go ahead and try it and see if it works in the first place. after that you can insert some simple counter to see how many times the code runs with respect to the size of the input strings.