What is the complexity (bigO) of this algorithm?

Question

This algorithm scans the line and tries to find another line. I suppose the logic is simple. Although I need help finding complexity.

int find(string mString, string lookUp) { int i, z, j, m = mString.size(), n = lookUp.size(), broken = 0, st = 0; for(j = 0, i = 0; i < m; i++) { if(mString[i] == lookUp[j]) { if(broken) { //go back and see if we're on the good path broken = 0; for(z = 0; z < j; z++) { if(broken) break; if(mString[iz] == lookUp[jz]) broken = 0; else broken = 1; } if(!broken) st = i - j + 1; } if(j + 1 != n) j++; } else broken = 1; } return st; } 

Can someone please help me?

Thanks.

Answer 1

When you work with large O and loops, I ask myself the question:

How many times, at best, can each cycle be performed?

In your example

• The outer loop will work at most `m` times.
• The inner loop will work at most `n` times.
• For each iteration of the outer loop, the inner loop will work at most `n` times

Does this help clarify your thinking?

Answer 2

O (n ^ 2) is the final complexity of this algorithm.