3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Tyler Jun 11 '17 at 21:03
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 11 '17 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.