1.) Use the Master Theorem (2-version) to give tight bounds, or argue why it is not...

 

Transcribed Image Text:

1.) Use the Master Theorem (2-version) to give tight bounds, or argue why it is not applicable. a. T(n) 4T(n/2) -n 4T(n/4) + 1/4 b. T(n) 4T(n/4) + O(1) c. T(n) = 8T(n/2) + n! d. T(n) 8T(n/2) + log n e. T(n) 2.) Solve using iteration: 3.) 4.) 5.) T(n)T(n-1)+4n Solve using substitution: T(n) = 2T(n-1)+4 What can you say about the time complexity of an algorithm whose run-time is given by this recurrence T(n) = 4T(n) + O(log n)? Which method might be most appropriate to solve the following recurrence? Use it to give its solution. T(n) = T(n/4) + T(3n/4) + cn 1.) Use the Master Theorem (2-version) to give tight bounds, or argue why it is not applicable. a. T(n) 4T(n/2) -n 4T(n/4) + 1/4 b. T(n) 4T(n/4) + O(1) c. T(n) = 8T(n/2) + n! d. T(n) 8T(n/2) + log n e. T(n) 2.) Solve using iteration: 3.) 4.) 5.) T(n)T(n-1)+4n Solve using substitution: T(n) = 2T(n-1)+4 What can you say about the time complexity of an algorithm whose run-time is given by this recurrence T(n) = 4T(n) + O(log n)? Which method might be most appropriate to solve the following recurrence? Use it to give its solution. T(n) = T(n/4) + T(3n/4) + cn