Search code examples
algorithmbig-omergesort

Determining number of calls (activations) to mergesort

I'm studying for a CS 125 final exam, and Big O Notation was covered (briefly).

Given that:

  • Mergesort has a Running Time Best Case of O(N lg(N)) and Running Time Worst Case of O(N lg (N))
  • There are 32 floating point values, initially in random order, stored in a double array

How many total calls(activations) to mergesort will there be if the array is to be sorted? Assume the base case sorts a single value.

I would go ahead and say simply plug in 32 to the worst case or best case (as mergesort guarantees O(N lg (N)).

This does not give me the correct solution (which is apparently 31). Can someone provide some pointers or an explanation? I just don't see it.

Solution

  • As 32 is 25, the recursion tree will be a full binary tree. We then do 1 + 2 + 4 + 8 + 16 + 32 = 63 calls to mergesort. It is unclear to me why the answer would be 31, when they state the base case is length 1. Apparently they don't count the last level of recursion (or they assume you don't recurse when the length is 1).

    In your original attempt, you are confusing running time with recursive calls. Mergesort's O(n log n) is an upper bound on the number of comparisons between elements the algorithm makes. As we want to count the number of recursive calls, knowing this bound doesn't do us any good (although knowing how the algorithm works does).