In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?

Question

In Strassen's algorithm, we calculate the time complexity based on n being the number of rows of the square matrix. Why don't we take n to be the total number of entries in the matrices (so if we were multiplying two 2x2 matrices, we would have n = 8 for the four entries in each matrix)? Then, using the naïve method of multiplying matrices, we would end up with only n multiplications and n/2 additions. For instance, multiplying [1 2, 3 4] by [5 6, 7 8] yields [1*5+2*7 1*6+2*8, 3*5+4*7 3*6+4*8]. Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n).
Of course, this reasoning is wrong because the time complexity cannot be linear but I don't understand why. I would appreciate any input. Thank you!

Answer 1

Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n).

That is wrong. It might work for a small example like $n = 8$, but for bigger ones it doesn't. E.g. if you have two square matrices with a total of $n = 200$ elements (two $10 \times 10$ matrices) you have already 1,000 multiplications, for $n=20\,000$ you have $1\,000\,000$.

---

Now to the actual question. It is possible to give the number time complexity in terms of the number of matrix elements, but it is not very practical.

One problem is, that the complexity differs a lot depending on the shape of the matrix:

• A multiplication of a $1 \times N$ matrix with a $N \times 1$ matrix has time complexity $O(N)$ (linear in the number of matrix elements).
• But a multiplication of a $N \times 1$ matrix with a $1 \times N$ matrix takes $O(N^2)$ (quadratic in the number of elements).

So it's a lot harder to argue about time complexities when you only know the number of elements.

And it's also easier to talk about the matrices in general. It feels more natural. E.g. saying "I've doubled the number of rows of the first matrix" makes sense to everybody (and you immediately know that the algorithm will run about twice as slow, "I've doubled the both dimensions of both matrices" makes sense. But saying "I've double the number of elements" will confuse anybody, how does the matrix look like afterwards. Did you increase both dimensions by a factor of 1.41? Did the matrix change shape? Or what happen? And what impact does it have on the runtime...

Answer 2

Short answer: because it's natural and convenient.

Longer answer: The number of multiplications to multiply a matrix of size p,q with a matrix of size q,r is pqr with a naive algorithm, and something more complicated with a smarter algorithm. The number of multiplications to multiply two square matrices of size n,n is n^3 with a naive algorithm, and n^(some number) with a smarter algorithm. So, we simplify everything by only considering square n,n matrices and expressing the complexity in function of n.

Note that it's not just with matrices that you have to be careful what "n" means:

• With graphs, it's common to have "n" be the number of vertices, which means the length of the input representing the graph is probably about n², depending on the number of edges and on the choice of representation.
• When the input is a string of digits representing a number, if N is the number and n is the length of the input representing that number, then n = log(N) and N = 2^n, so be very careful whether it is n or N in the complexity.
• There are algorithms with so-called pseudo-polynomial time complexity, which means they take exponential time with respect to the length of their input, but polynomial time with respect to the number represented by their input.
• There is a simple dynamic programming algorithm to solve the Knapsack problem in pseudo-polynomial time, which for some applications can be good enough; this algorithm is polynomial in the maximum weight capacity, but exponential in the number of digits of the maximum weight capacity, which really means it's exponential in the precision, the number of digits, that we're asking for.
• Factorising a number N into a product of primes is said to be very hard, yet obviously this can be done in sublinear time with respect to N: iterate on all numbers below √N and check if any of them divides N. This algorithm is sublinear in N, but exponential in the number of digits of N, so it's really exponential in the length of the input.

Answer 3

For n = 100, the naive algorithm takes 1,000,000 multiplications and almost as many additions. If we let n = number of rows / columns, then it takes $n^3$ multiplications and $n^3 - n^2$ additions. If we let $m = 2n^2$, that is the total number of elements in both matrices, then it is $m^{1.5} / 2^{1.5}$ multiplications and $m^{1.5} / 2^{1.5} - m/2$ additions. Both numbers are $O(m^{1.5})$ and not $O(m)$.

But the reason why we argue in the number of rows and columns, and not the problem size, is that the number of rows and columns usually follows naturally from the problem we try to solve. And in case of the Strassen algorithm which recursively divides a matrix into smaller sub matrices, its easier to reason that you need 7 matrix multiplications of half size. The algorithm is based on number of rows and columns and not on number of elements. And lastly, if the matrices don't have identical size, the number of calculations can easily be found from the numbers of rows and columns, but number of elements leaves a lot of room how many operations are needed, depending on the shapes of the matrices.

Answer 4

Because users of matrices think in terms of the matrix dimensions rather than the number of elements. Because that's related to the "size" of their problem in some way. E.g., you have n linear equations to solve, you're working in an n-dimensional space, ...

IOW matrices aren't interesting to work with as a bunch of elements in a rectangular shape and no other reason for existing - they're interesting to work with to use to solve some problem you have and that's why we study how fast you can compute with them. How "big" of a problem can you actually solve?

Answer 5

One aspect I'd like to stress in addition to the other answers (already covered to some extent there):

With the O(n) notation we express how the run time / memory consumption / ... changes if we change the "input size". But it's completely up to you how you define the term "input size", so you have to document this definition (and many CS sources take "the natural definition" for granted, so they feel they need not specify what n means).

Let's take multiplication of two large integers a simple example:

• If you define M to be the first integer and N the second, primary-school multiplication will give you a stunning O(logM logN) performance.
• But more often, M and N are defined to be the number of (e.g. decimal) digits in the integers, and then the same algorithm now counts as O(M N).

So, in your case, you can of course define N to be whatever you want, and then analyze how the run time changes if you supply inputs that vary in the aspect you called N. The results can be more or less useful, depending on your definition of N:

• If N is the value of the first entry of one of the arrays, changing N will not affect run time, and you get an O(1). Though this is a formally valid definition, you'll agree that it isn't helpful.
• If N is the maximum row or column size in one of the two matrices (a commonly-used definition), the naive multiplication takes O(N^3).
• If N is the number of entries of the bigger matrix (your suggestion), the same algorithm now has O(N^1.5). It hasn't become faster, you just redefined the meaning of N.