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?
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).
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)
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
