Algorithm Analysis Question 3) Write a pseudocode algorithm that searches for an

Question

Algorithm Analysis Question 3)

Write a pseudocode algorithm that searches for an item x in a sorted list of n items by dividing it into three sublists of almost n/3 items. This algorithm finds the sublist that might contain the given item and divides it into three smaller sublists of almost equal size. The algorithm repeats this process until it finds the item or concludes that the item is not in the list. (b) Let T(n) be the worst case complexity of the algorithm. Write a recurrence equation for T(n) and solve it to obtain the T theta complexity of T(n).

Explanation / Answer

Please let me know in case of any issue.

Algorithm:

// A recursive ternary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int ternarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l)/3;
int mid2 = mid1 + (r - l)/3;

// If x is present at the mid1
if (arr[mid1] == x) return mid1;

// If x is present at the mid2
if (arr[mid2] == x) return mid2;

// If x is present in left one-third
if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);

// If x is present in right one-third
if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);

// If x is present in middle one-third
return ternarySearch(arr, mid1+1, mid2-1, x);
}
// We reach here when element is not present in array
return -1;
}

The following is recursive formula for counting comparisons in worst case of Ternary Search.

T(n) = T(n/3) + 4, T(1) = 1

Time Complexity for Ternary search = 4clog3n + O(1)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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