# Need clarification about the use of Big-O to describe matrix sparsity

In one of my courses, Big-O notation was used for defining what a sparse matrix is, under the context of qualifying for suitability for a particular set of linear algebra algorithms. I looked around on the net, and only found more such uses that I have an issue with.

To say a matrix is sparse if it has O(n) non-zero elements, for example, is illogical. The sentence doesn't even parse right? When we talk about Big-O, we are talking about functions. So it would make sense to say for example, as a way to describe a property of a set of matrices, maybe produced by a function that builds or bounds particular types of matrices, parameterized by the dimensions. In this case however, it really would not say anything about a particular matrix in the set in terms of sparsity. For example, in such a O(n) set, every matrix of size less than 1 trillion^2 could have no non-zero elements.

I have the same logical problem with qualifications for graphs sparsity.

But I cannot seam to find any precise explanation for why Big-O is used in such ways, or whether it is used the correct way or is an abuse of notation.

What you have encountered is a very common convention. The sparsity assumption is probably in some algorithmic context: given a sparse matrix, here is an efficient algorithm that solves some problem. For example:

Given a matrix with $O(n)$ non-zero elements, there is an algorithm to do X in $O(n^2)$.

What this really means is:

For every $C > 0$ there is an algorithm that, given a matrix with at most $Cn$ non-zero elements, does X in $O(n^2)$.

The constant hidden inside the big O depends on $C$.

A similar convention explains the following sentence:

There is a function $f\colon \{0,1\}^n \to \{0,1\}$ whose maximal influence is $O(\log n/n)$.

(The meaning of maximal influence is not important here.) What this really means is:

There is a sequence of functions $f_1,f_2,\ldots$ such that $f_n\colon \{0,1\}^n \to \{0,1\}$ and the maximal influence of $f_n$ is $O(\log n/n)$.

Once you get used to this convention, all these seemingly meaningless sentences will acquire their full meaning.

• In this case, the algorithm was given, and was presented as efficient for matrices with O(n) non-zero elements. I suppose the instructor probably made a mistake (mixing up conventions)? – Tyler Jun 11 '17 at 21:03
• No, there was probably no mistake. Your instructor just used the very same convention. When run on matrices with at most $Cn$ zeroes, the algorithm is efficient. – Yuval Filmus Jun 11 '17 at 22:13