An algorithm to multiply two dense n times n matrices is On3

An algorithm to multiply two dense n times n matrices is O(n^3) Suppose a CPU takes 125 mu s to compute the product of two 1000 times 1000 matrices All things being equal, at most how long will it take to compute the product of two 5000 times 5000 matrices. When the dimension of the square matrices to be multiplied is doubled, by what factor will the time to compute the product change all things being equal.

Solution

a.) For n =1000; algo will take c*n^3 time i.e.
c * n3 = 125 * 10^(-6)
c = 125 * 10 ^(-6)}/(1000^3) = 125* 10 ^(-15)
now, for n = 5000, time will be c*n3 i.e.
125* 10 ^(-15) * (5000^3) = 15625 micro second = 15.625 ms

b.) When the dimension of the square matrices to be multiplies is doubled, time to compute the product will increase by 2^3 i.e., 8 times.

Hope it helps, do give your response.