(10 points) Suppose that we have two algorithms A1 and A2 for solving the same problem....

 

Transcribed Image Text:

(10 points) Suppose that we have two algorithms A1 and A2 for solving the same problem. Let T1(n) be the worst-case time complexity of A1 and T2(n) be the worst-case time complexity of A2. We know that {T (1)=1 Ti(n) 15 Ti(n/2)+ n, n>1 T(1) = 1 { T2(n) 80 T2(n/3) + 20 n, n>1. (a) Use the master method to get the running time for Ti(n). (b) Use the master method to get the running time for T(n). (c) Which algorithm is more efficient? Why? (10 points) Suppose that we have two algorithms A1 and A2 for solving the same problem. Let T1(n) be the worst-case time complexity of A1 and T2(n) be the worst-case time complexity of A2. We know that {T (1)=1 Ti(n) 15 Ti(n/2)+ n, n>1 T(1) = 1 { T2(n) 80 T2(n/3) + 20 n, n>1. (a) Use the master method to get the running time for Ti(n). (b) Use the master method to get the running time for T(n). (c) Which algorithm is more efficient? Why?