Question:
We can take advantage of a large number of processors by writing
procedures that work in parallel. The amount of time taken to do things
in parallel is the maximum amount of time taken for any one thing.
Say we have an algorithm to merge two arrays of length m and
n in O(log(m+n)) time.
// ParallelMerge takes an array arr with the first m elements in
// sorted order and the next n elements in sorted order. It puts all
// of arr into sorted order and takes O(log(m+n)) time.
void ParallelMerge(int *arr, int m, int n);
We can apply this to sorting using a parallel merge sort:
ParallelMergeSort(int *arr, int n) {
if(n == 1) return;
in parallel do {
ParallelMergeSort(arr, n / 2);
ParallelMergeSort(arr + n / 2, n - n / 2);
}
ParallelMerge(arr, n / 2, n - n / 2);
}
Write a recurrence for how long it takes to sort an array of length
n, and solve the recurrence using big-O notation.
Answer: The recurrence is
T(n) = T(n / 2) + O(log n)Its solution is T(n)=O( (log n)^2 ).