Review 2: Divide-and-conquer
printable version
Problem R2.1
In terms of n, the parameter, write a recurrence representing the amount of time taken by the below recursive algorithm. You can use variables C and D to represent constants that will vary from computer to computer.
def recur(n):
if n <= 1:
return n
else:
return recur(n - 1) + recur(n / 2)
| T(n) = { | C | if n ≤ 1 | |
| T(n − 1) + T(n / 2) + D | if n > 1 |
Problem R2.2
In terms of n, the length of the list parameter
nums, write a recurrence representing the amount of time taken by
the below recursive algorithm. You can use variables
C and D to represent constants that will
vary from computer to computer.
def recur(nums):
if len(nums) == 1:
return nums[0]
else:
i = nums / 4
j = nums / 2
k = 3 * nums / 4
return recur(nums[0:j]) - recur(nums[i:k]) + recur(nums[j:len(nums)])
(Recall that nums[a:b] computes and returns a
list containing the elements from nums indexed a through
b − 1. The
amount of time taken to construct this list is proportional to
b − a.)
| T(n) = { | C | if n = 1 |
| 3 T(n / 2) + D ⋅ n | if n > 1 |
Problem R2.3
The below method computes the largest distance between any two
points within a segment of the array pts, including all
array indices from start up to but excluding
end.
Write a recurrence T(n) that indicates the amount of time involved in the below program fragment; you do not need to reduce it to closed form. Justify your answer.
public static double biggestDist(Point[] pts, int start, int end) {
if(end - start <= 1) {
return 0;
} else {
int mid = (start + end) / 2;
double maxFirstHalf = biggestDist(pts, start, mid);
double maxSecondHalf = biggestDist(pts, mid, end);
double maxWithinHalf = Math.max(maxFirstHalf, maxSecondHalf);
double maxBetweenHalves = 0.0;
for(int i = start; i < mid; i++) {
for(int j = mid; j < end; j++) {
double d = pts[i].distance(pts[j]);
if(d > maxBetweenHalves) maxBetweenHalves = d;
}
}
return Math.max(maxWithinHalf, maxBetweenHalves);
}
}
| T(n) = { | C | if n ≤ 1 |
| 2 T(n / 2) + D n² | if n > 1 |
When the array segment has just one element, the method takes
O(1) time, which we represent here using
C.
Outside the base case, we have two recursive calls, each on an
array of length n / 2, so each of the two
recursive calls take T(n / 2) time.
Outside the recursive calls, the program goes through
n/2 iterations of the outer
i loop, and for each iteration there are
n / 2 iterations of the inner loop.
Thus, the method takes O(n²) time
outside the recursive invocations.
Problem R2.4
For each of the following recurrences, give its big-O bound in closed form.
| a. | T(n) = { | 6 | if n = 1 | |
| 8 T(n / 2) + n2.5 | if n > 1 | |||
| b. | T(n) = { | 10 | if n = 1 | |
| 9 T(n / 3) + n2.2 | if n > 1 | |||
| c. | T(n) = { | 3 | if n = 1 | |
| 8 T(n / 4) + n1.5 | if n > 1 |
| a. | O(n³) |
| b. | O(n2.2) |
| c. | O(n1.5 log n) |
Problem R2.5
For the below recurrence, give its closed-form big-O bound. Justify your answer, presumably by referencing the Master Theorem.
| T(n) = { | 6 | if n = 1 |
| 4 T(n / 4) + 0.5 n² + 2 n + 13 | if n > 1 |
O(n² log n). Mapping the recurrence to Master Theorem, we have a value for a of 4, for b of 2, and for d of 2. (We use 2 for d since 0.5 n² + 2 n + 13 = O(n²).) Since logb a is 2, which matches d, the answer according to the Master Theorem is O(nd log n).
Problem R2.6
Following is a poor implementation of merge sort in Java.
In terms of n, the number of elements in the parameter
ArrayList,
how fast is it on a single processor? Provide the simplest and tightest
big-O bound that you can, and justify your answer.
public static void mergeSort(ArrayList<Integer> nums) {
if(nums.size() <= 1) return;
ArrayList<Integer> a = new ArrayList<Integer>();
ArrayList<Integer> b = new ArrayList<Integer>();
for(int i = 0; i < nums.size(); i++) {
if(i % 2 == 0) a.add(nums.get(i));
else b.add(nums.get(i));
}
mergeSort(a);
mergeSort(b);
nums.clear();
while(!a.isEmpty() && !b.isEmpty()) {
if(a.get(0).intValue() < b.get(0).intValue()) nums.add(a.remove(0));
else nums.add(b.remove(0));
}
nums.addAll(a);
nums.addAll(b);
}
The overall time taken by this poor merge sort implementation is O(n²).
While the first loop still takes O(n)
time, the second loop — which performs the merge —
now takes O(n²) time. This is because it
repeatedly removes from the front of the ArrayList,
and each removal necessitates shifting all existing elements forward;
thus, each iteration of the loop takes O(n)
time, and there could be as many as n iterations of this
loop. As a result, we can build the following recurrence describing
the time for this method.
| T(n) = { | C | if n ≤ 1 |
| 2 T(n / 2) + D n² | if n > 1 |
This recurrence matches the form for the Master Theorem, with a = 2, b = 2, and d = 2. Since logb a (which is log2 2 = 1) is less than d, the Master Theorem says that the solution to this recurrence is O(n²).