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 &gt; 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.