How here the worst case complexity is O(m*(n-m+1))
from where (n-m+1) has come
Time complexity
Hello @Divya_321,
NAÏVE_STRING_MATCHER (T, P)
n ← length [T]
m ← length [P]
for s ← 0 to n-m do
j ← 1
while j ≤ m and T[s + j] = P[j] do
j ← j +1
If j > m then
return valid shift s
return no valid shift exist // i.e., there is no substring of T matching P.
Referring to the implementation of naïve matcher, we see that the for-loop in line 3 is executed at most n - m +1 times, and the while-loop in line 5 is executed at most m times. Therefore, the running time of the algorithm is O((n - m +1)m), which is clearly O(nm). Hence, in the worst case, when the length of the pattern, m are roughly equal, this algorithm runs in the quadratic time.
Hope, this would help.
Give a like if you are satisfied.
1 Like
is there any good source available to study time complexity
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.