Question

EC2 (5 Points): The running time of Algorithm Ais (1) n? + 1300, and the running time of another Algorithm B for solving the same problem is 112n - 8. Assuming all other factors equal, at what input sizes) would we prefer one algorithm to the other? 7.5 EC3 (2.5 Points): What is the recurrence relation (an equation that recursively defines) of the Towers of Hanoi problem? Remember, the base case is T(1) = 1 BIVAAI EE11

Answer 1

Q1. For n=0 to 11 : Runnning time of A>Running time of B : So we will prefer B in this interval.

For n=12 : Running time of A=Running time of B : So we can prefer any A or B

For n=13 to 435 : Running time of B>Running time of A : So we will preer A in this interval

For n=436 : Running time of A=Running time of B : So we can prefer any A or B

For n=437 to infinity : Runnning time of A>Running time of B : So we will prefer B in this interval.

Please find the explanation in the attached image

112n-8 . IS Value out When are -1300 = 112n-8. Given, Running time of A = (4) n² + 1300 Running time of B = We can calculate the stunning time for both the algorithmus and compare them to see, which one foster for a given of 'n'. we need to solve the given equations and find they equal. id)m2+1300 → 0.9502-12n +1308=0 values of a In=127 & 1n=436) running So now we need to check time of 4 is equal in interval [o,id], [13,435], running [437,00] . size (n) Running time Running time of 0(4) comparison (6)0341300 =!300 112(0)-8=28 Jo +!300-1300:24 7:20-8- loy This implies that we got on solving tu for which the time fB nput LO (B) . AB AB for this interval [o, sa] we should prefer Bon because time AB 11 its Questing 12 +1300 = 1330-29 12(1)-8=1224 1241300- 133612612) -8 21336 E)18+1300 = 1342.45 !12113)-8=1448 A=B A<B 13 for this interval 4 [13,435) we should prefer A because its = 48712 435 436 = 48606.25 = 48824 = 49042.25 = 48 824 ALB A=B A>B ช running time is less 437 -48936 Dua AB AB for this interval [437, 0] we should prefer B because its AYB А<B TA70 n=436 n20 n=12 no running time is less-

Q2 Please find the attached image

D2 Recurrence Relation for the Tower of Hanoi criven: No of moves T(1)-1 I ㅗ T(n)= 2T (n-1) + 1 T(n-1) = 2 (n-2) +} . Tin) = 2(2 T(n-2) + 1] + 1 I w N t e . w in twr L 7 Tintz 2 [2T (n-3) fI] + 1] +1 Tin) - 2[2C2 TN-3)+13+13+). = T(n) = 2[2[2[2T (0-4) ++] + 1] + 2] + 2 - T(0) = 24T (2-4) + - T(n) = 2* T (0-K) + 2 * _ 1 ) n is finite, kan lim T(n = 29-1 Since kan