Mergesort recurrence formulas - reconciling reality with textbooks

Question

I think this is more programming than math, so I posted here.

All the java algorithms in my question come from here.

We have an iterative and recursive merge sort. Both using the same merge function.

The professor teaching this lecture says that the critical operation for merge sort is the comparison.

So I came up with this formula for merge() based on compares:

>3n + 2

3: worst case compares through each loop.
n: amount of times loop will iterate.
2: the "test" compares.

The recursiveMergesort() has the base case compare plus the recursive calls for a total of:

>T(n/2) + 1 + 3n + 2 = T(n/2) + 3n + 3

The iterativeMergesort() simply has one loop that runs *n/2* times with a nested loop that runs n times. That leads me to this formula (but I think it's wrong):

>(n/2) * n + 3n + 2 = (n^2)/2 + 3n + 2

The books say that the recurrence formula for the recursive mergesort is

2T(n/2) + theta(n)

Which solves with the master method to

theta(NlogN)

Question 1: How are the formulas I created simplified to

T(n/2) + theta(n)

Question 2: Can I use any of these formulas (the ones I created, the textbook formula, or the time complexity *theta(nlogn)*) to predict number of compares when running this particular algorithm on an array size n

Question 3: For the bonus: Is my formula for the iterative method correct?

Merge:

private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
   // DK: add two tests to first verify "mid" and "hi" are in range
   if (mid >= a.length) return;
   if (hi > a.length) hi = a.length;
   int i = lo, j = mid;
   for (int k = lo; k < hi; k++) {
      if      (i == mid)     aux[k] = a[j++];
      else if (j == hi)      aux[k] = a[i++];
      else if (a[j] < a[i])  aux[k] = a[j++];
      else                   aux[k] = a[i++];
   }
   // copy back
   for (int k = lo; k < hi; k++)
      a[k] = aux[k];
}

Recursive Merge sort:

public static void recursiveMergesort(int[] a, int[] aux, int lo, int hi) {
   // base case
   if (hi - lo <= 1) return;
   // sort each half, recursively
   int mid = lo + (hi - lo) / 2;
   recursiveMergesort(a, aux, lo, mid);
   recursiveMergesort(a, aux, mid, hi);
   // merge back together
   merge(a, aux, lo, mid, hi);
}

public static void recursiveMergesort(int[] a) {
    int n = a.length;
    int[] aux = new int[n];
    recursiveMergesort(a, aux, 0, n);
}

Iterative merge sort:

public static void iterativeMergesort(int[] a) {
  int[] aux = new int[a.length];
  for (int blockSize=1; blockSize<a.length; blockSize*=2)
     for (int start=0; start<a.length; start+=2*blockSize)
        merge(a, aux, start, start+blockSize, start+2*blockSize);
   }

Wow, you made it all the way down here. Thanks!

Answer 1

Question 1:

Where are you getting your facts? To obtain theta(nlogn) complexity you need

T(n) = a T(n/b) + f(n), where a > 1, b > 1 and f(n) = cn + d. c != 0

Note: There are additional constraints, dictated by the Master theorem

You cannot derive from reccurence relation based on T(n) > T(n/2) + 3n + 3. You probably forgot that the cost of an array of size n is the cost of the merge plus twice the cost of each part. So rather

  T(n) = 2T(n/2) + 3n + 3

Question 2:

You cannot use theta, Big O or Big Omega to predict number of compares when running this particular algorithm on an array size n. Because they are asymptotic expressions. You need to solve the relation above, assuming it is correct.

For instance T(n) = 2T(n/2) + 3n + 3 has the solution

T(n) = 3n log2(n) + 1/2(c+6)n - 3, c constant

Still this is the number of comparisons of the algorithm. All optimizations and constraints of a real program are not considered.

Question 3: Nope