Binary search of a sorted array takes logarithmic search time, but the time to insert a new elementis linear in the size of the array. The time for insertion can be improved by keeping several sorted arrays.Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements. Let =, and let the binary representation of n be 1,₂, ...,₀>. We haveksorted arrays ₀,₁, ...,₁, where the length of array is 2. Each array is either full or empty,depending on whether =1 or 0, respectively. The total number of elements held in all k arrays is therefore . For example, when =10, its binary representation is , ₀ and ₂ are empty, and ₁ and ₃ are full with 2 and 8 elements respectively. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other. (1) Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time. (2) Describe how to perform the INSERT operation. Analyze its worst-case and amortized running times.

Transcribed image text