Summation Problem, Need help to continue.

72 Views Asked by At

Im working on certain problem, here is my effort:

enter image description here

My question is how do I continue this? any properties or rules could I use there?

I want to get the theta result for Brute Force String Matching algorithm which is O(mn)

I use this tutorial below as a reference to work on this

https://www.youtube.com/watch?v=4XkHbNi1ZL4

1

There are 1 best solutions below

0
On BEST ANSWER

Since $m$ and $n$ are fixed, you can say $$\sum_{i=0}^{n-m} \sum_{j=0}^{m}1 = \sum_{i=0}^{n-m} (m+1) = (n-m+1)(m+1)$$ which is indeed $O(mn)$, at least if you assume $n\ge m\gt 0$