Question

Algorithm. We divide each of the matrices A and B into 9 submatrices with size n/3 × n/3 each. The matrix C = A × B is obtained by using 25 multiplications and 30 additions of the submatrices. What is the recursive formula of the running time function T(n) of this algorithm? What is the running time of this algorithm (in Θ notation)?

Answer 1

Let a, b, c, d, e, f, g, h, i be the size of n/3 * n/3 submatrices of A.

and, a' , b' , c' , d' , e' , f' , g' , h' , i' be the size of n/3 * n/3 submatrices of B.

A,B,C is the matric of the size of n * n suct that A*B = C.

Given that the matrix C = A*B is obtained by using 25 multiplication and 30 addition of the submatrices ,

therefore the the recursiive formula of the running time function will according to the above method, in which we do 25 multiplications for matrices of size N/3 x N/3 and 30 additions since addition of two matrices takes O(N²) time. So the recursive  formula can be written as

T(N) = 25T(N/3) + o(N²)

The Running time complexity can be calculate by using Master Method which is as following

The master method works only for following type of recurrences that can be transformed to following type.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are following three cases:
1. If f(n) = Θ(n^c) where c < Log_ba then T(n) = Θ(n^Log_ba)

2. If f(n) = Θ(n^c) where c = Log_ba then T(n) = Θ(n^cLog n)

3.If f(n) = Θ(n^c) where c > Log_ba then T(n) = Θ(f(n))

So our Recursion Formula is:  T(N) = 25T(N/3) + o(N²)

where, we can say that ,

a =25 where a>=1

b=3 where b>1

and f(n) = O(N²) which implies that c=2

so let's calculate log_ba = log₃25 = log25 / log 3 = 2.93

therefore c < Log_ba which comes under case 1.

So Time complxity will be ,  T(N) =Θ(n^Log_ba) =Θ(n^Log₃25)