Yeah the paper uses O notation for complexity, but never when N is constant. For constant N and M, the paper uses the number of scalar multiplication operations performed as complexity measure. According to Figure 3, their algorithm has decreased the best known value from 49 to 47 for 4x4 matrices, and from 98 to 96 for 5x5 matrices (as well as some further state of the art improvements).

If you have to process many such matrices, you’re not at O(1). I would imagine that’s what the O is referring to in this case.

If you look at it that way then any algorithm is just o(n) where n is the number of matrices. O does not care about constant factors

There's a better explanation here: https://fgiesen.wordpress.com/2022/10/06/on-alphatensors-new...

This is for matrix multiplication where elements are themselves 4x4 matrices. So yes, indeed this is about multiplying many many 4x4 matrices where N is the size of the outer matrix.

To be pedantic, paper is very clear that O is calculated after decomposing arbitrarily large matrices to 4x4s.