## Question:

What is the complexity of the algorithm for finding a substring in a string, and how is it calculated? Please explain. (the algorithm is crude, but simplified as an example and for understanding)

```
text='bla-bla-this-bla'
subtext='this'
for i,element in enumerate(text):
if element == subtext[0]:
if subtext == text[i:i+len(subtext)]:
print(i)
```

## Answer:

Let:

```
n = len(text)
m = len(subtext)
```

It is obvious that the cycle `for`

make worst case `n`

iterations, in each iteration in the worst case we do slice `text[i:i+len(subtext)]`

, which is performed in O (m) , and then the comparison for the same O (m) , as a result we get O (nm).