A good definition is that the <sparse matrix> has non-zero entries proportional the number of rows. Therefore this is <Big O notation> less than something that has $N^2$ non zero entries. Of course, this only makes sense when generalizing to larger and larger matrices, otherwise we could take the constant of proportionality very high for one specific matrix.

Of course, this only makes sense when generalizing to larger and larger matrices, otherwise we could take the constant of proportionality very high for one specific matrix.


Discussion on "Dense and sparse matrices" by Ciro Santilli 32