Problem 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 \ldots q]$ is passed.

So:

  1. 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.
  2. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.

Binary search

  1. $T(n) = T(n/2) + c = \Theta(\lg{n})$ (master method)
  2. $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})$
  3. $T(n) = T(n/2) + cn = \Theta(n)$ (master method)

Merge sort

  1. $T(n) = 2T(n/2) + cn = \Theta(n\lg{n})$ (master method, duh)
  2. $T(n) = 2T(n/2) + cn + 2N = 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) $
  3. $T(n) = 2T(n/2) + cn + 2n/2 = 2T(n/2) + (c+1)n = \Theta(n\lg{n})$ (master method)