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-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 Excercise 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 problem and \(n\) be the size of a subproblem.

1. \(T(n) = T(n/2) + \Theta(1) \implies a = 1, b = 2\) and \(f(n) = 1\). We can use case 2 of the master method because \(f(n) = \Theta(n^{\log_2 1}) = \Theta(0)\), and thus the solution to the recurrence is \(T(n) = \Theta((n^{\log_2 1}) \lg n) = \Theta(\lg n)\).

2.

\[\begin{split} T(n) & = T(n/2) + \Theta(N) \\ & = T(n/4) + 2 \Theta(N) \\ & = T(n/8) + 3 \Theta(N) \\ & = \sum\limits_{i=0}^{\lg{n-1}}((i+1)\Theta(N)/2^i) \\ & = \Theta(N) \lg N \\ & = \Theta(N \lg N) \\ \end{split}\]

3. \(T(N) = 2T(N/2) + \Theta(N) \implies a = 1, b = 2\) and \(f(N) = N\). We can use case 3 of the master method because \(f(N) = \Omega(N^{\log_2 1 + \epsilon}) \implies \epsilon = 1 > 0\) and

\[\begin{split} af(N/b) && \leq cf(N) \\ (N/2) && \leq cN \\ \end{split}\]

holds for \(\frac{1}{2} \leq c < 1\). Thus the solution to the recurrence is \(T(N) = \Theta(f(N)) = \Theta(N)\).

b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.

1. \(T(n) = 2T(n/2) + \Theta(1) \implies a = 2, b = 2\) and \(f(n) = 1\). We can use case 2 of the master method because \(f(n) = \Theta(n^{\log_b a }) = \Theta(n^{\log_2 2 }) = \Theta(1)\), and thus the solution to the recurrence is \(T(n) = \Theta(n^{\log_b a} \lg n) = \Theta(n \lg n)\).

2.

\[\begin{split} T(n) &= 2T(n/2) + cn + 2\Theta(N) \\ &= 4T(n/4) + 2cn + 4\Theta(N) \\ &= 8T(n/8) + 3cn + 8\Theta(N) \\ &= \sum\limits_{i=0}^{\lg{n-1}} (i+1)cn + N\sum\limits_{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{split}\]

3. \(T(N) = 2T(n/2) + cn + 2n/2 = 2T(n/2) + (c+1)n\). This is the same recurrence as in part 1, thus the solution is \(\Theta(n \lg n)\).