Abstract—Search is a challenging concept in algorithms. It is challenging because striking the balance between performance and optimality is tough. Various numeric search techniques have been proposed, but achieving low time and space complexity is the main problem. A data structure and an algorithm should be thought of as a unit, neither one making sense without the other . In this approach, a new data structure Binary Cube (BC) and an algorithm named Crux have been proposed for achieving the balance as stated. The proposed algorithm has a constant time complexity of one. The space complexity is minimal when compared to traditional approaches. The best, worst and average time complexity of the proposed search is O (1) for all the three. This performance is achieved using the proposed data structure, BC, which has been created specifically to render this high level of efficiency.
Index Terms—Space complexity, Time complexity.
Manuscript received August 2010. Shrivatsan Rajagopalan is with the SSN SASE, Chennai 603110, India.( Phone: +91-09789545260; e-mail: nshrivatsan@ gmail.com).
Dr. F. Sagayaraj Francis, is currently an Associate Professor with the Department of Computer Science, Pondicherry Engineering College, Pondicherry, 605014, India (e-mail:email@example.com).
Cite: Shrivatsan Rajagopalan and F. Sagayaraj Francis, "Crux Search," International Journal of Engineering and Technology vol. 2, no. 5, pp. 408-411, 2010.