Algorithm Problem (Amortized Analysis): Please provide more detail for learning purposes.

Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is 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 k =[lg(n + 1)], and let the binary representation of n be . We have k sorted arrays A0, A2, ...,Ak-1, where the length of array A is 21. Each array is either full or empty, depending on whether n; = 1 or 0, respectively. The total number of elements held in all k arrays is therefore Ekon; 2 = n. For example, when n = 10, its binary representation is , A, and A2 are empty, and A4 and Az 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