Asymptotics don't have to be tight. It is still correct to say that matrix
inversion is O(n^3). But I agree it would be good to note that this is not
the best possible bound.


On Wed, Aug 21, 2013 at 9:49 PM, Jason Grout <notifications@github.com>wrote:

> In Algorithms/Matrices_Complexity/Matrices_Complexity.tex:
>
> >  given an input of size n.  Certain problems can be solved with fewer steps,
> > -whilst others require many more.  For example, given two matrices of size n,
> > -it only takes about n steps to add the entries together and thus matrix addition is $O(n)$.
> > -On the other hand, given a matrix of size $n$, it takes about
> > -$n^3$ steps to calculate its inverse,
> > +while others require many more.  For example, given two matrices of size n,
>
> Matrix multiplication and matrix inversion have the same asymptotic
> complexity (see Handbook of Linear Algebra, chapter 47, for references, or
> numerous places online or look in a convenient numerical linear algebra
> textbook). Let's say that matrix multiplication is complexity O(n^w). In
> the 60s it was proved that w<2.81 (Strassen), and more recent advancements
> have shown w<2.38. In the last few years, there are claims that w<2.7323.
> It's an open question how close matrix inversion and multiplication is to
> w=2. In short, it's not right to say that matrix inversion is O(n^3).
>
> —
> Reply to this email directly or view it on GitHub<https://github.com/byuimpact/numerical_computing/pull/266/files#r5915994>
> .
>



-- 
Abe Frandsen