September 4, 2008

**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.

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

- (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.

- (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?