The quaternary search algorithm is a modification of the binary search algorithm

Question

The quaternary search algorithm is a modification of the binary search algorithm that splits the input not into two sets of almost-equal sizes, but into four sets of sizes approximately one-fourth.
a) Verbally describe and write pseudo-code for the quaternary search algorithm.
b) Give the recurrence for the quaternary search algorithm
c) Solve the recurrence to determine the asymptotic running time of the algorithm. How does the running time of the quaternary search algorithm compare to that of the binary search algorithm.

Explanation / Answer

psedo code for quaternary search algorithm

This algorithm works by dividing the array into four equal parts. Hence, three elements are obtained. The specified element is then compared to those three elements. If any of them match with the required element, the position of that element in the array is obtained. We need a general formula for dividing the array into four equal parts.

Quaternary search is a very efficient search algorithm. It can be used in many real life applications. It requires the data to be sorted in either ascending or descending order. It can be used to for very large amounts of data. Quaternary search is more effective than binary search in most cases. It also saves up a lot of space compared to a binary tree. The basic idea behind this search algorithm is that it repeatedly divides the array into four equal parts and searches for the required number.

Recurrence for the quaternary search alogorithm

T(N)=T(N/4)+c

The running time (assuming constant-time comparisons and the RAM machine model) is O(lgn),Because the base is 4 here, for quaternary searches it becomes O(log4n)

T(N) = T(N/4) + 1

T(N/2) = T(N/8) + 1

T(N/4) = T(N/16) + 1
…
T(8) = T(2) + 1

T(4) = T(1) + 1

Next we sum up the left and the right sides of the equations above:

T(N) +T(N/2) + T(N/4) + ........+ T(8) + T(4) =

T(N/4) + T(N/8) + T(N/16) + … +T(2) + T(1) + (1 + 1 + … + 1)

The number of 1’s on the right side is LogN

Finally, we cross the equal terms on the opposite sides and simplify the remaining sum on the right side:

T(N) + T(N/2) = T(1) + 1

Therefore the running time of binary search is:

T(N) = O(Log4N)

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.