42 Parameterpassing costs
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 parameterpassing 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 subrage that might be accessed by the called procedure. Time $= \Theta(q  p + 1)$ if the subarray $A[p..q]$ is passed.
a. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.35). Give recurrences for the worstcase 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 problems and $n$ be the size of a subproblem.
b. Redo part (a) for the $\text{MERGESORT}$ algorithm from Section 2.3.1.
a.
 $T(n) = T(n / 2) + c = \Theta(\lg n)$. (master method)

$\Theta(n\lg n)$.
$$ \begin{aligned} T(n) & = T(n / 2) + cN \\ & = 2cN + T(n / 4) \\ & = 3cN + T(n / 8) \\ & = \sum_{i = 0}^{\lg n  1}(2^icN / 2^i) \\ & = cN\lg n \\ & = \Theta(n\lg n). \end{aligned} $$

$T(n) = T(n / 2) + cn = \Theta(n)$. (master method)
b.
 $T(n) = 2T(n / 2) + cn = \Theta(n\lg n)$. (master method)

$\Theta(n^2)$.
$$ \begin{aligned} T(n) & = 2T(n / 2) + cn + 2N = 4N + cn + 2c(n / 2) + 4T(n / 4) \\ & = 8N + 2cn + 4c(n / 4) + 8T(n / 8) \\ & = \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) \\ & = \Theta(n^2). \end{aligned} $$

$\Theta(n\lg n)$.
$$ \begin{aligned} T(n) & = 2T(n / 2) + cn + 2n / 2 \\ & = 2T(n / 2) + (c + 1)n \\ & = \Theta(n\lg n). \end{aligned} $$