I am studying the time complexity of an algorithm to find if a string n contains a substring m where m <= n. The result of the analysis is that the time complexity is O(nm). So taking this time complexity as starting point and knowing that m <= n, thus mn <= n^2. Can we say that time complexity in big-O notation is O(n^2).
1 Answers
It is indeed the case that if the runtime of a function is O(mn) and you know for a fact that m ≤ n, then the runtime of the function is O(n2).
However, this may not be the best way of characterizing the runtime. If m is a tunable parameter that can range from, say, 0 to n, then O(mn) could be a "better" way of characterizing the runtime. For example, suppose this is an algorithm that finds the m smallest elements out of an n-element array. If you want to use this algorithm to find the top five elements (m = 5) out of ten million (n = 106), then characterizing the runtime as O(n2) would greatly overestimate the actual amount of work done, while O(mn) would give a better bound on the runtime.
In the case of string searching, the fact that the two strings can have wildly different lengths is a good reason to characterize the runtime as O(mn), as it shows you how the runtime scales with the runtime of both of the input strings, not just one of the strings.
Hope this helps!
Related