Big-O Notation For Coding Interviews and Beyond/

...

/

Solution Set 3

Solution Set 3

Solutions to problem set 3

We'll cover the following...

Solution 1

a-

We can implement merge sort by dividing the initial input array into 3 subproblems instead of 2. The only caution we need to exercise is to carefully pass the boundaries for the three parts in the subsequent recursive portions. Combining the three arrays is equivalent of solving the problem of merging n number of sorted arrays, using a priority queue. One way the algorithm can be implemented is shown below.

Java
import java.util.Random;
import java.util.PriorityQueue;
class Demonstration {
    public static void main( String args[] ) {
        createTestData();
        long start = System.currentTimeMillis();
        mergeSort(0, input.length - 1, input);
        long end = System.currentTimeMillis();
        System.out.println("Time taken = " + (end - start));
        printArray(input);
    }
    private static int SIZE = 100;
    private static Random random = new Random(System.currentTimeMillis());
    static private int[] input = new int[SIZE];
    static PriorityQueue<Integer> q = new PriorityQueue<>(SIZE);
    private static void printArray(int[] input) {
        System.out.println();
        for (int i = 0; i < input.length; i++)
            System.out.print(" " + input[i] + " ");
        System.out.println();
    }
    private static void createTestData() {
        for (int i = 0; i < SIZE; i++) {
            input[i] = random.nextInt(10000);
        }
    }
    private static void mergeSort(int start, int end, int[] input) {
        if (start >= end) {
            return;
        } else if (start + 1 == end) {
            if (input[start] > input[end]) {
                int temp = input[start];
                input[start] = input[end];
                input[end] = temp;
            }
            return;
        }
        int oneThird = (end - start) / 3;
        // sort first half
        mergeSort(start, start + oneThird, input);
        // sort second half
        mergeSort(start + oneThird + 1, start + 1 + (2 * oneThird), input);
        // sort third half
        mergeSort(start + 2 + (2 * oneThird), end, input);
        // merge the three sorted arrays using a priority queue
        int k;
        for (k = start; k <= end; k++) {
            q.add(input[k]);
        }
        k = start;
        while (!q.isEmpty()) {
            input[k] = q.poll();
            k++;
        }
    }
}

b-

How many recursion levels will the be generated?

Say we are provided with an array of size n. The question we need to ask ourselves is how many times do we need to successively divide n by 3 to get to 1? If there are 9 elements, we'll divide once to get 3 and then one more time to get 1. This can be expressed as a logarithmic equation as follow:

log3n=xlog_3n = x

The number of levels of the recursion tree will be 1 more than log3n so the correct answer would be log3n + 1.

c-

The recurrence equation will be given as:

T(n)=Cost to divide into 3 subproblems+3∗T(n3)+Cost to merge 3 subproblemsT(n) = Cost\:to\:divide\:into\:3\:subproblems + 3*T(\frac{n}{3}) + Cost\:to\:merge\:3\:subproblems

We determined in the previous question the number of recursion levels for the 3-way merge sort will be log3n+1. Next, we need to determine the cost to merge the three subproblems. Unlike in traditional merge sort, the 3-way merge sort uses a priority queue to create a min-heap before attempting a merge of the three subproblems. Insertion into a priority queue takes lgn time and since we insert all the n elements into the queue, the total time to create the heap comes out to be nlgn. Finally, the cost to divide the problem into three subproblems is constant and can be represented by d. Therefore, the time complexity will be:

T(n)=(log3n+1)∗(d+nlgn)T(n) = (log_3n+1)*(d+nlgn)

T(n)=dlog3n+d+nlgnlog3n+nlgnT(n) = dlog_3n+d+nlgnlog_3n+nlgn

T(n)=O(nlgnlog3n)T(n) = O(nlgnlog_3n)

Since lgn > log3n, we can simplify to:

T(n)=O(n(lgn)2)T(n) = O(n(lgn)^2) ...