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?=??(1).

2. An array is passed by copying. Time?=??(N), where?N?is the size of the array.

3. An array is passed by copying only the sub range that might be accessed by the called procedure. Time?=??(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 an= n be the size of a sub problem.

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

Section 2.3.1

Transcribed Image Text:

1 1 let YL[1..Y.length] and YR[1.Y. length] be new arrays 2 YL.length = YR.length = 0 3 for i = 1 to Y.length if Y [i] € PL Y1.length = Y1.length + 1 YL[YL.length] = Y [i] else YR.length = YR.length + 1 YR[YR.length] = Y [i] 4 5 7 8