# Confusion over the complexity of parameter passing in merge sort

I'm working through CLRS on problem 4-2, which says the following:

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself.

This problem examines the implications of three parameter-passing strategies:

1. An array is passed by pointer. Time $= \Theta (1)$.
2. An array is passed by copying. Time $\Theta (N)$, where $N$ is the size of the array.
3. An array is passed by copying only the subrange that might be accessed by the called procedure. Time $= \Theta(q-p+1)$ if the subarray $A[p \ldots q]$ is passed.

Consider the recursive merge sort algorithm. Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let $N$ be the size of the original problem and $n$ be the size of a subproblem.

For part (2), one solution I have seen is:

$$T(n) = 2T(n/2) + cn + \color{red}{2N} = \color{blue}{4N} + cn + 2c(n/2) + 4T(n/4) = 8N + 2cn + 4c(n/4) + 8T(n/8) = \\ \qquad = \sum_{i=0}^{\lg{n}-1}(cn + 2^iN) = \sum_{i=0}^{\lg{n}-1}cn + N\sum_{i=0}^{\lg{n}-1}2^i = cn\lg{n} + N\frac{2^{\lg{n}} - 1}{2-1} = cn\lg{n} + nN - N = \Theta(nN) \\ \qquad = \Theta(n^2)$$

I don't understand where the $\color{red}{2N}$ has come from. The $2T(n/2)$ is the "conquer" part, and the $cn$ is the "combine" part, leaving the $\color{red}{2N}$ to be the "divide" part, but I'm not sure why it's $2N$ rather than just $N$, as you are only copying the $N$-length arrary over once.

Also, I don't understand where the $\color{blue}{4N}$ has come from (following the previous equality). Surely, $$T(n) = 2T(n/2) + cn +2N \\ = 2\underbrace{[2T(n/4) + c(n/2) + 2N ]}_{T(n/2)} + cn + 2N \\ = 4T(n/4) +2cn + 6N \ ?$$

Finally, am I right in thinking that the last equality holds because $N$ is some subset of $n$, so $n$ = $k N$ (for some constant $k$), so $T(n) = \Theta(n) \cdot \Theta(N) = n \cdot n = n^2$?

• The question can't be answered without consulting the specific pseudocode. – Raphael Feb 1 '18 at 11:51

The $N$ is incurred once for every recursive call, since this is the cost of passing a parameter. Since there are two recursive calls, it's $2N$. As for the $4N$, this seems like a mistake. Don't expect solutions you find on the internet to be correct. Finally, $N$ is not a subset of $n$. It is the size of the original array. A less confusing way to write the conclusion would be $\Theta(nN) = \Theta(N^2)$. Note that it is always the case that $n \leq N$ (and not the other way around).

• So are the two recursive calls the $D(n)$ part of $T(n) = aT(n/b)+C(n) + D(n)$? Also, should I replace $N$ with $n$, and $n$ with $N$ in my solution? – Spongebob Aug 5 '17 at 8:11
• i.e. should it be $$T(N) = 2T(N/2) + cN + 2n \ ?$$ – Spongebob Aug 5 '17 at 8:13
• No. You should think of $N$ as a constant, and of $n$ as a parameter, since $n$ keeps changing, while $N$ stays constant. – Yuval Filmus Aug 5 '17 at 9:09

I'm not sure how they got the $4N$ term either, but here's a simpler analysis. Let $T(n)$ be the cost of a recursive call of size $n$. We separate the costs of sorting, $S(n)$, and passing parameters, $P(n)$. We have:

• $T(n) = S(n) + P(n)$
• $S(n) = 2S(n/2) + cn$
• $P(n) = 2P(n/2) + N$

Solving by standard methods yields $T(n) \in \Theta(n^2)$.

• Why is $P(n)$ not just equal to $N$? Could you elaborate on "standard methods"? I can't use the master method because there are two recursive calls ($2S(n/2)$ and $2P(n/2)$) rather than one. – Spongebob Aug 5 '17 at 8:19
• Also, I seem to be mixing up my $n$ and my $N$ terms. Can I write the whole thing as a function of $n$ only (or $N$ only)? – Spongebob Aug 5 '17 at 8:20
• Why would it be equal to just $N$? It has recursive calls. Also, you would use the master theorem (or whatever else) on each recursive equation separately. And, no, you can't. $n$ and $N$ are different things. – quicksort Aug 5 '17 at 8:23
• But that doesn't contradict the fact that it has recursive calls. If $T(n) = 2T(n/2) + cn + N$, then N is still going to increase with $n$, as $T(n/2)$ contains $N$. Also, you would eventually have that $T(n) = \Theta (nN)$ or something like that. How would you reason from this that $T(n) = \Theta(n^2)$? Finally, I just realised that $N$ is the size of the original problem and $n$ is the size of a subproblem. Shouldn't the recursions therefore be functions of $N$, rather than $n$ (i.e. $T(N) = \ldots$? I'm confused... – Spongebob Aug 5 '17 at 8:34
• No, the recursions are functions of both $N$ and $n$. There isn't any problem with that. You would solve the $S$ and $P$ recursions separately and then add them. The $S$ part is $\Theta(n \log n)$ and the $P$ part is $\Theta(n^2)$, yielding quadratic complexity overall. – quicksort Aug 5 '17 at 8:40