Solving the duplicates problem via divide and conquer.

Recall the has_dups problem: given an array, determine if there are any duplicates in the array and return true if there are and false otherwise (in which case all elements are distinct).

On the next page is a divide-and-conquer approach to the problem.

The idea is simple:

Recursively determine if the left half has any duplicates

Recursively determine if the right half has any duplicates

If neither half has duplicates, there may still be a duplicate -- one copy on the left and one on the right.

determine if this is the case by looping through the candidate pairs (one from left; one from right).

Your Job:

(A) Write a recurrence relation for the runtime of this algorithm. Explain each component of the recurrence relation.

(B) Use the recursion tree method (as we did with MergeSort) to derive a tight (big-Theta) bound on the worst-case runtime of the algorithm.

(C) Discuss: how does this approach compare with the simple approach you know from Homework 1?

// subarray a[lo...hi]. N

bool _has_dups(int a[], int lo, int hi) {

int i, j, m;

bool ldups, rdups;

if(hi <= lo) return false; // zero or one element: no dups!

m = (lo + hi)/2;

ldups = _has_dups(a, lo, m);

rdups = _has_dups(a, m+1, hi);

if(ldups || rdups)

return true;

// could still be dups: one on left & one on right

for(i=lo; i<=m; i++) {

for(j=m+1; j<=hi; j++) {

if(a[i]==a[j]) return true;

}

}

return false;

}

bool has_dups(int a[], int n){

return _has_dups(a, 0, n-1);

}