[Big-O] Additional Problems #12

[rygh4775]

The following code computes the intersection (the number of elements in common) of two arrays. It assumes that neither array has duplicates. It computes the intersection by sorting one array (array b) and then iterating through array a checking (via binary search) if each value is in b. What is its runtime?

int intersection(int[] a, int[] b) {
    mergesort(b);
    int intersect = 0;
    for (int x : a) {
        if (binarySearch(b, x) >= 0) {
            intersect++ ;
        }
    }
    return intersect;
}

[tgi01054]

Two expensive operation are merge sort and binary search. Each time complexity is below.

• Merge sort: O(b * log b)
• Binary search O(log b)

For binary search, it is repeated by a times.

Answer is O(b log b) + a O(log b) = O(blog b + a log b)

CTCI book shows that answer is O(b log b + a log b). But it can be simplified as O( (a+b)log b).

For case a >> b, log b can be very smaller than a. O(a) can be answer. For case a << b, a + b can be simplified by b. O(b * log b) can be answer.