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:
A pointer to the array is passed to the sorting function,
The entire array is copied to a separate location before applying the sorting function,
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!