CPSC 411: Quiz 2
September 4, 2008
"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."
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?