Is O(mn) in O(n^2)?

Question

Simple question. Working with an m x n matrix and I'm doing some O(mn) operations. My question is if O(mn) is in O(n^2). Looking at the Wikipedia on big O I would think so but I've always been pretty bad at complexity bounds so I was hoping someone could clarify.

Answer 1

O(mn) for a m x n matrix means that you're doing constant work for each value of the matrix.

O(n^2) means that, for each column, you're doing work that is O(# columns). Note this runtime increases trivially with # of rows.

So, in the end, it's a matter of if m is greater than n. if m >> n, O(n^2) is faster. if m << n, O(mn) is faster.

Answer 2

m * n is O(n²) if m is O(n).

I assume that for matrix you probably will have m = O(n) which is the number of columns while n is a number of rows. So m * n = O(n²). But who knows how many columns your matrix will have.

It all depends on what bounds does m have.

Have a look at definition of O(n).