Imagine the following data structure:

A pair of arrays where one array is longer than the other, and both arrays are kept sorted. The length of the shorter array is the square root of the length of the longer array; although, it may have empty entries if it is not yet full. To add an element, you use insertion sort to insert the element into the shorter array. If the short array fills up, re-allocate the shorter and longer arrays and merge the two old arrays into the new longer array. The new short array is empty. Then, to find an element, use binary search on both the long and the short arrays.

I have worked out the following: For the given data structure, a search would consist of searching already sorted arrays (as the insertion operation assures they are inserted in proper order). Therefore, it is important to consider how the binary search operation is constructed. For a given list of n-elements, we are trying to search for specific element A.

Utilizing a divide and conquer approach, the algorithm continually halves the data set it is searching until the element is found. In a worst-case scenario, the worst-case scenario can be analyzed as the following (where n = number of elements and m = maximum number of times data set can be halved):

log_2⁡〖n= log_2⁡〖2^m 〗 〗
log_2⁡〖n= m〗

**However, my professor stated the following: ** However, there could be a situation in that the specified element is not contained in the larger array which would be searched first. Then, the smaller array would be searched, which would have a complexity of O(log⁡(n/2)). Thus, the overall complexity of searching for the elements will be O(log (n)).

I do not understand the highlighted portion at all. And, despite my searching in CLRS, cannot come up with anything that helps. Can someone explain why searching the smaller array is a O(log⁡(n/2)) time complexity and how the overall complexity of searching for the elements will be O(log (n))


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.