Last updated - Tues 5-27-2014
Problem 2 For this question to ensure that you are giving enough detail in your answer for step 1 and step 3, please give a full class definition including the constructor and fields etc.
Below here updated - Wed 5-21-2014
Problem 3 For this question you are not solving the recurrences exactly. We do not have all the constants needed. For example, in class we talked about the best case for parallel quicksort, using parallel partition and parallelism for the two recursive calls. We said this span was T(n) = O(log n) + T(n/2), which we said was O(log^2 n). Note that we described the contribution of parallel partition as O(log n). It is fine to treat this as log n, but keep in mind that it started out as O(log n) - it was not an exact value.
For both part a and part b, for both work and span, you should state a similar recurrence, and then solve it to give a big-O bound with the allowance that since you are solving for an upper bound you can ignore some constants (for example, approximate using a bigger value on the RHS if it helps).