Please explain how to find the recurrence of the following code. Why is the answ
ID: 3820966 • Letter: P
Question
Please explain how to find the recurrence of the following code. Why is the answer T(6n/7) + O(1) and how I can solve a similar question?
What is the recurrence for the worst-case runtime of the algorithm below?
The following algorithm takes as input a sorted array of integers A. left and right represent the left and right indicies of the array that is being searched. The parameter x represents an integer. The algorithm Search searches whether or not x is in the array A. If x is in the array, it returns the index of x. If x is not in the array, it returns -1. The function floor(a) returns the integer part of a. The initial call to Search is Search( A, 1, n, x ).
int Search(A,left,right,x) { numelements = right - left + 1;
if (numelements < 20) {
for (i = 0; i < numelements; i++){
if (A[left + i] == x) return (left + i);
}
return (-1);
} else {
split = floor(numelements * 1/7) + left;
if (A[split] == x) return(split);
if (A[split] > x) return(Search(A,left,split-1,x));
if (A[split] < x) return(Search(A,split,right,x)); } }
Explanation / Answer
Why is the answer T(6n/7) + O(1) and how I can solve a similar question?
if (numelements < 20) {
for (i = 0; i < numelements; i++){
if (A[left + i] == x) return (left + i);
}
return (-1);
}
If we see this if part, it has size of element 20 and doing constant operation (may be some small multiple of 20) so this is a constant operation.
Now lets see else part
split = floor(numelements * 1/7) + left;
if (A[split] == x) return(split);
if (A[split] > x) return(Search(A,left,split-1,x));1/7th of the size problem
if (A[split] < x) return(Search(A,split,right,x)); } } 6/7 of the size problem
So T(n) = T(n/7) + T(6n/7) + O(1)
You are missing n/7 term in the equation.
Apply method I just demonstrated in this question to solve similar questions.