Number of flops required to invert a matrix

Question

I have an n-by-n upper triangular matrix $R$ and I can calculate its inverse by back substitution. I cannot make myself see why it needs $O(n^{3}/3)$ flops to do so. Can you explain?

Answer 1

Why matrix inversion by Jordan-Gauss elimination scales as $O(n^3)$ is quite well-explained here on Wikipedia; see if you can understand it from there - I doubt I could do better myself.

Now about your $O(n^3/3)$: note that it takes approximately $2n^3/3$ operations to invert a generic matrix. For a triangular matrix, it takes half the number of operations, hence the $n^3/3$ in your book.

A final note: while saying that something takes $kn^3$ operations is fine, writing $O(n^3/3)$ is quite strange. This is because the big-O notation was introduced precisely to do away with having to specify constants, since complexity theory is mainly concerned with how algorithms scale. In practice, of course, knowing the constant can be very important (compare $2^n$ with $1000n$ for $n=3$, say); I'm just saying that the notation is strange.