Do different variants of Mergesort have different runtime?

Question

One of my courses introduced the following question:

Given the recurrence relation for mergesort:

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

How would the following parameter passing strategies influence the relation and running time of the algorithm:

1. A pointer to the array is passed to the sorting function,

2. The entire array is copied to a separate location before applying the sorting function,

3. A subsection of the array is copied to a separate location before applying the sorting function on that subsection.

For 1., since this is how mergesort is used most of the time, we can solve it easily using the master theorem.

$f(n) = \Theta(n^{\log_b a}) = \Theta(n) \implies T(n) = \Theta(n \log n)$

For 2. however, I am a bit baffled. Although we do an additional work of $O(n)$, we are only doing so once at the beginning of the sort. Hence, doing one additional instance of $O(n)$ work should not influence the order of the running time (because it already is of a larger order). Hence, for both 2. and 3. the running time would remain at $T(n) = \Theta(n \log n)$.

Is this reasoning valid? Something tells me that the $O(n)$ copying should have more of an impact, but I can't seem to give myself a good enough reason that it should be responsible to slow it down enough so that it would worse (i.e. $O(n^2)$).

Any thoughts or hints would be quite appreciated!

Answer 1

Note first that we are talking about an algorithmic idea here; in order to apply a meaningful analysis, we would need at least pseudocode for the three variants.

Note furthermore that the given recurrence is most likely only valid in the limit. It is also not clear what the complexity measure is. Comparisons? In that case, it is clear that none of the adaptions change the measure at all. Basic operations? That would make more sense.

1. I agree with your reasoning; this seems to be the basic variant. Note again, however, that you'd have to look in the actual algorithm for its analysis. In particular, applying Mergesort in-place is uncommon.

2. Copying the entire array once adds a linear term globally, so the recurrence does not change. If you are only after $\Theta$-behaviour, ignore it (since the actual algorithm dominates).

3. Now this adds linear overhead to every call of the routine, changing the recurrence from $\ldots + n$ to something like $\ldots + 2n$. Of course, this results only in a different constant so the result is again not influenced (see Master Theorem).