Matrix multiplication (continued) The(min, +)multiplication is associative, and with the real numbers it forms an algebraic structure called a closed semiring Consequently, we can compute D(1)=D0)·A=A1 0(2)=D D(n-1)=D(n-2)·A=A yielding D()=(&i, D) Time =o(n'n)=0(n). No better than n x B-F c 2001 by Charles E Leiserson Introduction to Agorithms Day 32 L19.7© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.7 Matrix multiplication (continued) The (min, +) multiplication is associative, and with the real numbers, it forms an algebraic structure called a closed semiring. Consequently, we can compute D(1) = D(0) · A = A1 D(2) = D(1) · A = A2 M M D(n–1) = D(n–2) · A = An–1 , yielding D(n–1) = (δ(i, j)). Time = Θ(n·n3) = Θ(n4). No better than n × B-F