---

4. (15 points) Sort n integers in {0, 1, …, t-1} can be done with p processors (a) in O(loglogn) time. (b) in O(logn) time. (c) In constant time. (d) in O(n/p+logn) time. (e) in O((n/p+logn)logt/loglogn) time. (f) in O(n/p+loglogn) time.

5. (10 points) Sorting n numbers in {0, 1, …, (logn)3} with p processors can be done in (a) O(logn) time. (b) O(n/p+logn) time. (c) O(nloga/(plog(n/p)) +logalogn/log(n/p)) time. (d) O(nlogn/p+logn) time. (e) O(na/p+alogn) time. (f) O(nloga/p+logalogn) time.

6. (15 points) Linked list prefix for linked list of n elements can be computed using n processors in (a) O(logn) time. (b) O(n/p+logn) time. (c)O(loglogn) time. (d) O(logloglogn) time. (e) Constant time. (f) O(log(logp/log(p/n))) time. (g) O(n/p+log2n) time.