The question:
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:
- 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.
- 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.
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 problem and n be the size of a subproblem.
b. Redo part (a) for the MERGE-SORT algorithm from Section 2.3.1.
I have trouble understanding how to solve the recurrence of case 2 where arrays are passed by copying for both algorithms.
Take the binary search algorithm of case 2 for example, the recurrence most answers give is T(n)=T(n / 2)+Theta(N). I have no trouble about that.
Here is an answer I find online that looks correct:
T(n)
= T(n/2) + cN
= 2cN + T(n/4)
= 3cN + T(n/8)
= Sigma(i = 0 to lgn - 1) (2^i cN / (2^i))
= cNlgn
= Theta(nlgn)
I have trouble understanding how the second last line can result in the last line's answer. Why not represent it in Theta(Nlgn)? And how can N become n in the Theta notation?
N and n feel somewhat connected. I have trouble understanding their connection and how that is applied in the solution.
Seems that N represents full array length and n is current chunk size.
But formulas really exploit initial value only, when you start from full length n=N - for example, look at T(n/4) for T(N/4), so n===N everywhere.
In this case you can replace n with N.