why is the time complexity of square matrix multiplication defined as O(n^3)?

Question

I have come across this in multiple sources (online and books) - Running time of square matrix multiplication is O(n^3) for matrices of size nXn. (example - matrix multiplication algorithm time complexity)

This statement would indicate that the upper bound on running time of this multiplication process is C.n^3 where C is some constant and n>n0 where n0 is some input beyond which this upper bound holds true. (http://en.wikipedia.org/wiki/Big_O_notation and What is the difference between Θ(n) and O(n)?) Problem is, i cannot seem to derive the values of constants C and n0.

My questions -

1. Can someone provide a mathematical proof for the statement 'big Oh of square matrix multiplication is O(n^3)' ?

2. what are the values of C and n0 ?

Answer 1

1. There are 3 for loops within each other going from 0 to n-1 (or 1 to n) each (as can be seen in the link you provided, even though it's not completely correct), this results in O(n³). Formalizing it into a proper proof should be easy enough.

2. a) For a formal proof, running time needs to be defined in terms of some set of operations, commonly taken to be any arithmetic operation. Inside the 3 for loops there are 2 arithmetic operations (1 multiplication, 1 addition), thus we get 2.n3, thus C = 2.

   b) n0 = 0 because this holds true from n = 1

Note that, since big-O is just an upper bound, we can also say the complexity of this algorithm is O(n^k) for any k >= 3 (the same would not be true if we use big-Theta notation). We can also take C and n0 to be any value greater than 2 and 0 respectively (since the requirement isn't to find the smallest possible values).