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:
- 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..q]\) is passed.
- 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 problem and \(n\) be the size of a subproblem.
- Redo part (a) for the \(\textsc {Merge-Sort}\) algorithm from Section 2.3.1.
Understanding the Setup
Before diving into the analysis, let’s clarify the key distinction: \(N\) represents the size of the original array we start with, while \(n\) represents the size of the current subproblem we’re working on. For example, if we start with an array of 1000 elements (\(N = 1000\)) and recursively process half of it, the subproblem has \(n = 500\) elements. This distinction is crucial for understanding Method 2, where we always copy the entire original array regardless of subproblem size.
A. Binary Search
Recall that binary search works by checking the middle element of a sorted array and then recursively searching either the left or right half, depending on whether the target is smaller or larger than the middle element.
Method 1: Pass by Pointer
When we make a recursive call using pointers, we’re simply passing the memory address of where the subarray starts. No matter how large the original array is, passing an address is just passing a number. A single piece of information.
Think of it like using a dictionary: instead of photocopying pages when telling someone where to look, you just say “check pages 100-200.” This takes constant time regardless of how many pages are in that range.
We are solving one subproblem of half the size, and the overhead of passing the pointer is constant. So the recurrence equation for this will be:
\[T_1(n) = T_1(n/2) + \Theta(1)\]Using the master theorem with \(a=1, b=2, f(n) = \Theta(1) = \Theta(n^{\log_2 1}) = \Theta(n^0)\), case 2 applies:
\[T_1(n) = \Theta(\lg n)\]This is the familiar binary search time complexity we all know.
Method 2: Copy Entire Array
This is the most wasteful approach. Every time we make a recursive call, even when we’re only searching through 500 elements, then 250, then 125, and so on. We copy the entire original array of \(N\) elements.
Imagine you’re searching for a word in a 1000-page dictionary. After looking at page 500, you know the word is in the first half. But before continuing your search, you make a complete photocopy of all 1000 pages again! Then when you narrow it down to pages 1-250, you photocopy all 1000 pages yet again. It’s incredibly wasteful, but that’s exactly what Method 2 does.
Again, we are solving one subproblem of half the size, but the overhead of copying the complete array is dependent on the length of the array, \(N\). So the recurrence equation for this will be:
\[T_2(n) = T_2(n/2) + \Theta(N)\]Intuitively, binary search makes \(\lg n\) recursive calls (cutting the problem in half each time until we reach a single element). At each of these \(\lg n\) levels, we pay \(\Theta(N)\) to copy the entire array. Therefore:
\[T_2(n) = \Theta(N \lg n)\]Notice how much worse this is: instead of \(\Theta(\lg n)\), we have a factor of \(N\) multiplied in!
Method 3: Copy Subrange
This is a middle-ground approach. When we recursively search the left half of a 1000-element array, we only copy those 500 elements. Then when we search the left half of that (250 elements), we only copy those 250 elements, and so on.
Using our dictionary analogy: when you determine the word is in pages 1-500, you photocopy just those 500 pages. When you narrow it to pages 1-250, you photocopy just those 250 pages. Much better than Method 2, but still not as efficient as just passing a pointer.
Again, we are solving one subproblem of half the size, but the overhead of copying the complete array is now dependent on the length of the current subrange, \(n\). So the recurrence equation for this will be:
\[T_3(n) = T_3(n/2) + \Theta(n)\]Using the master theorem with \(a=1\) and \(b=2\):
\[\begin {align*} f(n) &= \Theta(n) \\ &= \Omega(n) \\ &= \Omega(n^{0 + \epsilon}) \text{ for } \epsilon = 1 > 0 \\ &= \Omega(n^{\log_2 1 + \epsilon}) \\ &= \Omega(n^{\log_b a + \epsilon}) \end {align*}\]For case 3 to apply, we also need to verify the regularity condition: \(a \cdot f(n/b) \leq c \cdot f(n)\) for some \(c < 1\). Indeed, this holds true for \(c = 1/2\):
\[1 \cdot \Theta(n/2) = \Theta(n/2) \leq (1/2) \cdot \Theta(n)\]Therefore, case 3 applies:
\[T_3(n) = \Theta(n)\]
B. Merge Sort
Recall that merge sort works by recursively dividing the array into two halves, sorting each half, and then merging the sorted halves back together. Unlike binary search which makes one recursive call, merge sort makes two recursive calls, one for each half.
Method 1: Pass by Pointer
Just like with binary search, passing pointers is efficient. When we split an array into left and right halves, we just pass the starting addresses of each half; no copying needed. The only real work is the merging step, which requires examining all \(n\) elements in the current subproblem to combine the two sorted halves.
We are making two recursive calls, each on half the data, and then merging the results. So the recurrence equation for this will be:
\[T_1(n) = 2T_1(n/2) + \Theta(n)\]Using the master theorem with \(a=2\) and \(b=2\):
\[\begin {align*} f(n) &= \Theta(n) \\ &= \Theta(n^1) \\ &= \Theta(n^{\log_2 2}) \\ &= \Theta(n^{\log_b a}) \end {align*}\]Therefore, case 2 applies:
\[T_1(n) = \Theta(n \lg n)\]This is the standard merge sort time complexity we know and love.
Method 2: Copy Entire Array
This is where things get really bad. Remember, merge sort makes two recursive calls at each level, not just one like binary search. Let’s trace what happens with a concrete example.
Suppose we start with an array of \(N = 16\) elements:
- Level 0 (root): We copy 16 elements once before splitting. Cost: \(1 \times N = 16\) copies
- Level 1 (two halves): Each of the 2 recursive calls copies all 16 elements again. Cost: \(2 \times N = 32\) copies
- Level 2 (four quarters): Each of the 4 recursive calls copies all 16 elements. Cost: \(4 \times N = 64\) copies
- Level 3 (eight eighths): Each of the 8 recursive calls copies all 16 elements. Cost: \(8 \times N = 128\) copies
The pattern is clear: at level \(i\), we have \(2^i\) subproblems, and each one copies all \(N\) elements.
We are making two recursive calls, each on half the data. The overhead includes copying the entire original array (\(\Theta(N)\)) and merging the results (\(\Theta(n)\)). So the recurrence equation for this will be:
\[T_2(n) = 2T_2(n/2) + \Theta(N) + \Theta(n)\]The recursion tree has \(\lg n\) levels (since we split in half each time). At level \(i\), there are \(2^i\) nodes, each copying \(N\) elements:
- Level \(0\): \(2^0 \times N = N\)
- Level \(1\): \(2^1 \times N = 2N\)
- Level \(2\): \(2^2 \times N = 4N\)
- …
- Level \(\lg n - 1\): \(2^{\lg n - 1} \times N = (n/2) \times N\)
Total copying cost across all \(\lg n\) levels:
\[\begin {align*} \sum_{i=0}^{\lg n - 1} 2^i \cdot N &= N \sum_{i=0}^{\lg n - 1} 2^i \\ &= N(2^{\lg n} - 1) \\ &= N(n - 1) \\ &= \Theta(Nn) \end {align*}\]The merging across all levels adds \(\Theta(n \lg n)\), but this is dominated by \(\Theta(Nn)\). Therefore:
\[T_2(n) = \Theta(Nn)\]Method 3: Copy Subrange
This method is more reasonable. When we split a 1000-element array, we copy the left 500 elements for one recursive call and the right 500 elements for the other. When we further split those, we copy 250 elements for each of the four subproblems, and so on.
Let’s think about the total copying cost at each level:
- Level 0: Copy \(n\) elements (split into left and right halves)
- Level 1: Copy \(n/2 + n/2 = n\) elements total (across both subproblems)
- Level 2: Copy \(n/4 + n/4 + n/4 + n/4 = n\) elements total (across four subproblems)
At each level, we copy a total of \(\Theta(n)\) elements! This is the same cost as merging.
We are making two recursive calls, each on half the data. The overhead includes copying the subarrays (\(\Theta(n)\) total across both calls) and merging (\(\Theta(n)\)). So the recurrence equation for this will be:
\[T_3(n) = 2T_3(n/2) + \Theta(n) + \Theta(n)\]Simplifying:
\[T_3(n) = 2T_3(n/2) + \Theta(n)\]This is identical to Method 1’s recurrence! Using the master theorem with \(a=2\) and \(b=2\):
\[\begin {align*} f(n) &= \Theta(n) \\ &= \Theta(n^{\log_2 2}) \\ &= \Theta(n^{\log_b a}) \end {align*}\]Therefore, case 2 applies:
\[T_3(n) = \Theta(n \lg n)\]
Summary and Key Takeaways
The table below summarizes the running times for both algorithms under the three parameter-passing methods:
| Algorithm | Method 1 (Pointer) | Method 2 (Copy All) | Method 3 (Copy Subrange) |
|---|---|---|---|
| Binary Search | \(\Theta(\lg n)\) | \(\Theta(N \lg n)\) | \(\Theta(n)\) |
| Merge Sort | \(\Theta(n \lg n)\) | \(\Theta(Nn)\) | \(\Theta(n \lg n)\) |