For the following algorithms given in schematic form, write down a divide-and-conquer recurrence relation for the run ti

[answerhappygod]

For the following algorithms given in schematic form, write downa divide-and-conquerrecurrence relation for the run time, and solve for the runtime.(a) FUNCTION F1 ( X, n ) {Split X into X1 and X2Y1 = F1 ( X1 , n / 2 )Y2 = F1 ( X2 , n / 2 )Combine ( Y1 , Y2 )}If Split and Combine has runtime of Θ(n) then F1 has aruntime(b) FUNCTION F2 ( X, n ) {S p l i t X i n t o Y1 , Y2 , Y3T e s t ( Y1 , Y2 )depending on the outcome o f testDO F2 ( Y1 , n / 3 )o r F2 ( Y2 , n / 3 )o r F2 ( Y3 , n / 3 )}If Split takes Θ(n2) and Test takes Θ(1) then F2 has runtime(c) FUNCTION F3 ( b )Split and b into three equal parts b0 , b1 , b2F3 ( b0 )F3 ( b2 )Combine the results of the sub problemsIf Split has O(1) and Combine has Θ(n) run time then F3 hasruntime