Solution Found!
Parameter-passing costs Throughout this book, we assume
Chapter 4, Problem 4-2(choose chapter or problem)
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 D .1/. 2. An array is passed by copying. Time D .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 D .q p C 1/ if the subarray Ap : : 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.
Questions & Answers
QUESTION:
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 D .1/. 2. An array is passed by copying. Time D .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 D .q p C 1/ if the subarray Ap : : 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.
ANSWER:Step 1 of 7
Binary Search algorithm is always applied on sorted array. This algorithm is based on divide and conquer technique. The algorithm searched a target value in the sorted array. Merge-Sort algorithm is also based on the divide-and-conquer approach. It is used to sort the set of elements in an array.