Review 2: Divide-and-conquer: Questions

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)
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.)

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);
    }
}
R2.4.

For each of the following recurrences, give its big-O bound in closed form.

a. T(n) = { 6if n = 1
8 T(n / 2) + n2.5if n > 1
b. T(n) = { 10if n = 1
9 T(n / 3) + n2.2if n > 1
c. T(n) = { 3if n = 1
8 T(n / 4) + n1.5if n > 1
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
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);
}

Review 2: Divide-and-conquer: Solutions

R2.1.
T(n) = { Cif n ≤ 1
T(n − 1) + T(n / 2) + Dif n > 1
R2.2.
T(n) = { Cif n = 1
3 T(n / 2) + D ⋅ nif n > 1
R2.3.
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.

R2.4.
a. O(n³)
b. O(n2.2)
c. O(n1.5 log n)
R2.5.

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).

R2.6.

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²).