Problem 2: (6 points) The quaternary search algorithm is a modification of the b

Question

Problem 2: (6 points) 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

a) Quatenary search is an searching algorithm employed on sorted arrays and is a modification of the binary search algorithm. Its working is similar to the binary search save that it repeatedly divides the search interval into four (approximately) equal parts. Three 'quater points' are thus obtained and the specified element is compared with them. If any of them match the required element, the position of that element in the array is obtained. Else the search interval is accordingly modified.

Pseudocode:

QSearch(A[n], value, low, high)           //Do NOT misread QSearch as Quick Search.
    while high ? 1                                 // A is the array of size n, high and low are intitially n-1 and 0 respectively
        p1 = low + ((high – low) / 4)         //first quarter point
        p2 = low + ((high – low) / 2)         //second quarter point
        p3 = low + (3*(high – low) / 4)        //third quarter point
        if A[p1] == value
            return p1                                 //returns the position of value
        else if A[p2] == value
            return p2
        else if A[p3] == value
            return p3
        else if A[p1] > value
            return QSearch(A, value, low, p1-1)
        else if A[p2] > value
            return QSearch(A, value, p1+1, p2-1)
        else if A[p3] > value && value > A[p2]
            return QSearch(A, value, p2+1, p3-1)
else                        //if A[p3] < value
            return QSearch(A, value, p3 + 1, high)

b) As the algorithm examines all four subproblems, and each is one quarter the size of the entire array, the reccurence relation is T(n) = T(n/4) + c

c) Solving the reccurence ralation, the time time complexity of the quaternary search algorithm is O(logn). Although at first sight it may seem that it is same as that of the binary search algorithm, it is important to note that the running time of binary search is actually O(log2n) whereas in quatenary search it is O(log4n). This makes the QSearch faster than binary search.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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