Empirical Analysis of Quaternary and Binary Search

Abstract

This paper presents an empirical analysis between traditional binary search and quaternary search algorithm in sorted arrays. Binary search algorithm divides the list into two equal halves each time, whereas quaternary search technique divides it into four segments each time. An experiment was conducted with an objective to search the element which is causing the worst time complexity in case of sorted array. It was observed through experiment results that iterative binary search is better than recursive binary search, iterative quaternary search is better than recursive quaternary search and definitely iterative quaternary search is better than iterative binary search. So, the evaluation results prove the best time complexity of binary search algorithm is O(log2 n) and quaternary search algorithm has the best time complexity of O(log4n) and therefore, it’s decided that quaternary search algorithm is better in searching as compared to binary search algorithm.