Big-O notation with 2 variables. Given m <= n, can we reduce O(nm)?

Question

Assuming m <= n, can you reduce O(nm) to O(n)?

I would think not, since m can be equal to n

In the case of m < n, I would think that O(nm) can be reduced to O(n) since m is strictly less than n and hence becomes insignificant as n approaches infinity

Am I correct in my above assumptions? If so, why? What is the more formal way of showing this?

Answer 1

If m is a constant (E.g.: 2) or lower than a constant, you are right: O(mn) = O(n).

But because you wrote m < n, I suppose that m also goes to infinite, but slower than n.

In this case, you are wrong.

Consider m = log(n) as an example and everything should be clear.

O(mn) = O(n*log(n))

which is different than O(n).

That would be true for O(m+n), but not for O(mn).

Answer 2

Given m <= n, all you can say about O(mn) is that it's O(n**2) at worst.

If m is bounded by a constant, O(mn) becomes O(n)

Answer 3

Simply you can not reduce the O(m*n) to O(n). If there is no boundary condition on m.

m < n It means m can be anything between 0 to n-1.

Let's say that m is bounded and it value ca not grow more than C

m <= C

In this case

O(m*n) can be reduced to O(n)

P.S : Do read this plain english big o notaion