For the following algorithms given in schematic form, write down a divide-an d-c
ID: 3725170 • Letter: F
Question
For the following algorithms given in schematic form, write down a divide-an d-conquer recurrence relation for the run time, and solve for the run time in Big Theta form. PROCEDURE MULTC a, b, n) Split a into a0, a, and b into b0, b1 MULT a0, b0, n/2): MULT a0, bl, n/2) MULTC a1, b1, n/2) MULT a1, b0, n/2) MULT( a a0, bi b0, n/2) COMBINE the results of the subproblems If Split and COMBINE have (n) run time then MULT has runtime FUNCTION FOOL( X, n) Split X into X1 and X2 Y1 = FOOL(X1, n/2) Y2 FOOL(X2, n/2) COMBINE(Y1, Y2) If SPLIT and COMBINE are both (n) then FOOL has runtime FUNCTION MESS X, n) Split X into Y1, Y2, Y3 TESTC Y1, Y2) depending on the outcome of TEST DO MESS( Y1, n/3) or MESSC Y2, n/3) or MESS Y3, n/3) If SPLIT takes (n2) and TEST takes (1) then MESS has runtimeExplanation / Answer
Answer is provided below, please follow the answer.
Answer:a)
PROCEDURE MULT( a, b, n)
Split a into a0, a1, and b into b0, b1 ------- > constant time
MULT( a0, b0, n/2): MULT( a0, b1, n/2) ------- > T(n/2)
MULT( a1, b1, n/2): MULT( a1, b0, n/2) ------- > T(n/2)
MULT( a1 + a0, b1 + b0, n/2) ------- > (n2/4)
[due to running time of addition of two n/2 x n/2 matrices]
COMBINE the results of the sub problems ---- > (n)
If Split and COMBINE have (n) run time then MULT has runtime :
T(n)= 3T(n/2) + (n2)
By master theorem, T(n)= 3T(n/2) + (n2)
As, a=3, b=2
So that (nlog23 ) = (n 1.58) ~ (n2)
Answer: b)
FUNCTION FOOL( X, n)
Split X into X1 and X2 ------ > constant time
Y1 = FOOL(X1, n/2) ------- > T(n/2)
Y2 = FOOL(X2, n/2) -------- >T(n/2)
COMBINE(Y1, Y2) -------- > (n) due to T(n/2 +n/2)=T(n)
If SPLIT and COMBINE are both (n) then FOOL has runtime :
T(n) =2 T(n/2) + (n)
=2(2T(n/4) + n/2) + n = 4T(n/4) + n + n = 4T(n/4) + 2n
= 4(2T(n/8) + n/4) + 2n = 8T(n/8) + n + 2n = 8T(n/8) + 3n
= .. ..
= n*T(1) + log2(n)*n
= (n*log2(n))
Answer:c)
FUNCTION MESS( X, n)
Split X into Y1, Y2, Y3 ------- > (n 2 )
TEST( Y1, Y2) ------- > (1)
depending on the outcome of TEST
DO MESS( Y1, n/3) ----- > (n 2 /9)+ (1 ) = (n 2 )
or MESS( Y2, n/3) ----- > (n 2 /9)+ (1 ) = (n 2 )
or MESS( Y3, n/3) ----- > (n 2 /9 )+ (1 ) = (n 2 )
If SPLIT takes (n 2 ) and TEST takes (1) then MESS has runtime:
T(n) = (n 2 )+ (1 ) + (n 2 )+ (n 2 )+ (n 2 )
= (n 2 )