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:
  
  
  An array is passed by pointer. Time $ = \Theta (1)$.
  An array is passed by copying. Time $\Theta (N)$, where $N$ is the size of the array.
  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 $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).