Need clarification about the use of Big-O to describe matrix sparsity
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.