4-2 Parameter-passing 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 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 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.3-5). 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 problems and $n$ be the size of a subproblem.

b. Redo part (a) for the $\text{MERGE-SORT}$ algorithm from Section 2.3.1.

a.

1. $T(n) = T(n / 2) + c = \Theta(\lg n)$. (master method)

2. $\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}$$

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

b.

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

2. $\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}$$

3. $\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}$$