The 2-Key Case

About 10 and a half years back, when I was an summer student in IMSC (Institute of Mathematical Science) my mentor(Dr. Venkatesh Raman) asked a question to ponder during my first weekend in the institute and let him know how to solve it.

Before I go into the problem: I will give a background for it.

Predominately, there are 2 problem in Computer Science: Searching and Sorting. "How to do it efficiently ?"

"implicit data structures" - these data structures uses very little or no extra spaces other than the "data elements".

For example, "linked list" which use 1 pointer per "data elements" will amount to the "Space Complexity" of SizeOf(data_elements) + ((Number of data_elements) * SizeOf(Pointer)).

ie.. if the input is N integers, the "Space Complexity" of the integer linked list = N + N (pointers for each integer)
= 2*N

The Space Complexity of a Binary Search Tree (BST) = N + 2 N (2 pointers for each data_element)
= 3*N

But, a Sorted Array is an "Implicit Data Structure", it does not store any extra space. Whereas if you take the "Time Complexity" of both BST and Sorted Array for searching an element in the Collection, it takes same time which is lg(N).

lg = log N to the base 2