Question

Question 1. Solving Recursive Relations [3 mark]. A naive multiplication of two matrices of order n requires O(nᵒ) additions. By using a divide and conquer approach, Strassen devised another algorithm that requires T(n) additions where T(n) = 7T(n/2)+cna, where c is a constant independent of n and T(1) = 0 (as multiplying two numbers re- quires no additions). Use the method of backward substitution (introduced in Week 2's lecture) to show that Strassen’s algorithm requires O(nlog27) = O(n2.81) additions, which is better than O(nº). Provide all the steps of your proof to get your mark (make sure you use T(1) = 0 in your proof). Note that there is the so-called Master Theorem to deal with a general recurrence relation of the type T(n) = aT(n/b) + O(n"), where a,b,c are con- stants (see Levitin's textbook Chapter 5). However, here it is required that you present the method of backward substitution to understand how a proof of the Master Theorem should work.

Answer 1

Solution:
Using substitution method prove that T(n) = 7T(n/2) + cn² has O(n^log₂7) complexity.
O(n^log₂7) = O(n^2.81) (approx.)

Substitution Method:

In the substitution method, we make a guess for the solution and then we use mathematical induction to prove the guess is incorrect or correct.

For example consider the recurrence T(n) = 2T(n/2) + n

We guess the solution as T(n) = O(nLogn). Now we use inductionto prove our guess.

We need to prove that T(n) <= cnLogn. We can assume that it is true for values smaller than n.
 
T(n) = 2T(n/2) + n
    <= cn/2Log(n/2) + n
    =  cnLogn - cnLog2 + n
    =  cnLogn - cn + n
    <= cnLogn

Now solving our problem.

T(n) = 7T(n/2) + cn²

As given in the question we guess the solution as O(n^log₂7). Now we use induction to prove our guess.

We need to prove that T(n) <= cn^log₂7. We assume that it is true for the values smaller than n.

T(n) = 7T(n/2) + cn²
<= c(n/2)^log₂7 + cn²
<= c(n^log₂7 - 2^log₂7) + cn²

As we know that: b^logb^(x) = x. Therefore, 2^log₂7 = 7.
Then,
T(n) <= c(n^log₂7 - 7) + cn²
<= cn^log₂7 - 7c + cn²
As c is constant therefore assume 7c = c.

So,
T(n) <= cn^log₂7 + cn² - c

As n^log₂7 > n². So we take O(n^log₂7) as our solution.

Hence T(n) = O(n^log₂7) or T(n) = O(n^2.81) is our required solution.