Boyer-Moore Substring Search Worst Case

Question

I had a quiz question on my school

"Boyer Moore algorithm has the worst-case time complexity O(MN) where M is the length of the string and N is the length of the pattern."

it is True False question and i answered False for the statement above because i always read that N is the lenght of text and M is the lenght of pattern but my instructor says it doesn't matter how you define M and N so because of it claims statement is True is it correct ? if not how can i prove him that statement is false scientifically ?

Answer 1

Your instructor is right. Changing the names doesn't matter at all, the time complexity is M * N. It's everything simplified to the expression that: 'the order of factors doesn't change the product'.

If M and N are inverted, complexity is still N * M or M * N.

It would be completely different if the time complexity were, for example O (M^2 log N), then yeah, if you invert what M means and N means, the complexity is completely different.

Answer 2

When we write a mathematical expression and then follow up with "where M is something and N is something", we're explicitly defining what M and N mean when we use them in this text. It doesn't matter whether other texts use different letters to mean those things because our text stands alone. Now that might be confusing, because here O(...) itself is a standard notation. It's implicit from context (that we're talking about time complexity) what O(...) means, and there's nothing here to override that. But really the only convention regarding variable names is that we generally use N if there's one relevant dimension of the input to measure and M and N if there are two, but regardless we still need to say what we're assigning them to.