Binary search of a sorted array takes logarithmic search time, but the time to insert a new
Question:
Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements. Let k = [lg (n + 1)], and let the binary representation of n be nk-1, nk-2, ..., n0. We have k sorted arrays A0, A1, ..., Ak-1, where for i = 0, 1, ..., k - 1, the length of array Ai is 2i. Each array is either full or empty, depending on whether ni = 1 or ni = 0, respectively. The total number of elements held in all k arrays is therefore. Although each individual array is sorted, there is no particular relationship between elements in different arrays.
a. Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time.
b. Describe how to insert a new element into this data structure. Analyze its worst-case and amortized running times.
c. Discuss how to implement DELETE.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Related Book For
Data Structures and Algorithm Analysis in Java
ISBN: 978-0132576277
3rd edition
Authors: Mark A. Weiss
Question Posted: