7

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 ?

Community
  • 1
  • 1
Quest Monger
  • 8,252
  • 11
  • 37
  • 43
  • For each cell (n^2), you will go through n cells in the corresponding rows and columns and multiply them together, so it's O(n^3). – nhahtdh Nov 22 '12 at 07:00
  • so if we have 2 matrices A and B each is nXn. and their product is matrix X of size nXn. you are implying that for each value in X (there are n^2 values in X) you have to traverse a total of n elements in A and B ? or is that more like n elements in A and n elements in B, which would make this n^4 and not n^3. – Quest Monger Nov 22 '12 at 07:09
  • n elements in A and n elements in B, yes, but it totals up to 2n, not n^2. So the final result is O(n^3). – nhahtdh Nov 22 '12 at 07:39

1 Answers1

8

  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(n3). 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(nk) 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).

Community
  • 1
  • 1
Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • 1
    thanks! and thank you for correcting my mistake, i meant an asymptotic upper bound. sorry for confusion. relevant - http://mathforum.org/library/drmath/view/51904.html – Quest Monger Nov 25 '12 at 00:29
  • @QuestMonger thank you so much for the mathforum link... that was the most easy to understand answer I have yet to come across! – Titus Aug 28 '14 at 16:57