Why time complexity of brute force algorithm is O(n*m)?

Question

I am using the following brute force algorithm for searching a string inside another string.

As I know, the number of comparisons is (n-m+1)*m in the worst case, but the right answer for time complexity is supposed to be O(n*m).

To get this answer, I do the following transformations:

(n-m+1)*m = (n+1) * m - m^2 = O(n*m) - m^2

How do you get O(n*m) from here?

Where did -m^2 go?

Brute force algorithm:

NAIVE-STRING-MATCHER

n = T.length
m = P.length
for s = 0 to n - m
    if P[1...m] == T[s+1...s+m]
        print s

Answer 1

The running time indeed belongs to O(m(n-m)). But as the Big-O notation is an upper bound, this is also O(mn), as mn ≥ m(n-m).

In practice, no harm is done by this simplification, as you usually expect the length of the search string to be proportional to that of the pattern. Then m = αn yields m(n-m) = mn(1-α).