0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ We can see a string of equalities but we have no idea what you're doing or where you're going with this. You probably have time to explain before it's closed for improvement, if you move fast. You should probably review this before further posting, too. $\endgroup$
    – rschwieb
    Sep 21, 2021 at 14:17
  • $\begingroup$ @rschwieb I made some edit there, hopefully it is help. $\endgroup$
    – Al_Muzakier
    Sep 21, 2021 at 14:25
  • 2
    $\begingroup$ $m$ is constant in the sum so you can take it out of the sum. $\endgroup$
    – kingW3
    Sep 21, 2021 at 14:30

1 Answer 1

Reset to default
0
$\begingroup$

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$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.