This is my recursive search function in Java int terSearch(int arr[], int l, int

Question

This is my recursive search function in Java int terSearch(int arr[], int l, int r, int x) that returns location of x in a given sorted array arr[l…r] is present, otherwise -1. The terSearch search function, unlike the binary search, must consider two dividing points int d1 = l + (r - l)/3 int d2 = d1 + (r - l)/3

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);

} return -1;
}

can someone help wme with the following data structures question please

"(b) What is the running time complexity of your function? Justify. "

I just need to know the running time complexitiy of the function above, aloong with a justification/explanation

please help

Explanation / Answer

Since, your problem divides the problem in three equal parts (left one-third, middle one-third and right one-third). Hence, its recursive equation is

t(n) = t(n/3) + 1

From Master's theorem,

a = 1, b = 3, k =0

since, a = bk and p>-1 (case 2(a))

therefore, t(n) = O (nlogba * logbp+1n) = O(nlog 1 * log3n)

= O(log3 n)

Hope it helps, do comment in case of any query,

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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