3 For The Following Algorithms Given In Schematic Form Write Down A Divide And Conquer Recurrence Relation For The Ru 1 (185.98 KiB) Viewed 21 times
(3) For the following algorithms given in schematic form, write down a divide-and-conquer recurrence relation for the run time, and solve for the run time. (a) FUNCTION F1 X, n){ Split X into X1 and X2 Y1 = F1(X1, n/2) Y2 = F1(X2, n/2) Combine (Y1, Y2) } If Split and Combine has runtime of O(n) then F1 has a runtime (b) FUNCTION F2( X, n){ Split X into Y2, Y3 Test ( Y1, Y2) depending on the outcome of Test } DO Y1, F2( Y1, n/3) or F2 Y2, n/3) or F2 Y3, n/3)
If Split takes (n²) and Test takes (1) then F2 has runtime (c) FUNCTION F3(b) Split and b into three equal parts b0, bl, b2 F3( b0) F3( b2) Combine the results of the subproblems. If Split has O(1) and Combine has (n) run time then F3 has runtime
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!