Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."

Signature:___________________________________________

REFER TO MASTER THEOREM WRITTEN ON THE BOARD.

1. (2 pts) What is the divide and conquer paradigm?
   
   
   
   
   
   
   
   

2. (2 pts) If the pivots are chosen in quicksort so that the array is split exactly in half at each recursive step, then the recurrence describing the running time is T(n) = 2T(n/2) + n. Use the master theorem to come up with a closed form formula for T(n). Show your work.
   
   
   
   
   
   
   
   

3. (1 pt) In the worst case of quicksort, the pivot elements are chosen so that the recurrence describing the running time is T(n) = T(n-1) + n. Can the master theorem be used to solve this recurrence? Why or why not?