What is the recurrence for the worst-case runtime

Assignment Help Data Structure & Algorithms

Reference no: EM132095289

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

Reference no: EM132095289

Questions Cloud

Find the mean and standard deviation of a number of data : Write a program, using C#, that will find the mean and standard deviation of a number of data points.

Develop the code in a step-by-step manner : You may add other methods if needed, however, all the methods and the variables indicated in the UML diagram must be implemented.

Discuss about the penetration testing : In information security, penetration testing may be wrongly perceived as being a "hacker-like" activity.

Find the comments against each line for the description : Modify the program above program so that it contains a class related to the Leibniz formula. Add additional methods to the class .

What is the recurrence for the worst-case runtime : What is the recurrence for the worst-case runtime of the algorithm below?

Design the circuit using one rotate-right circuit : Design the circuit using one rotate-right circuit, one rotate-left circuit, and one 2-to-1 multiplexer to select the desired result. Derive the code.

Discuss ipv4 and ipv6 according to its capabilities : Discuss IPv4 and IPv6 according to its capabilities to address a single device on any network in the world and how it correlates to the Internet of Things.

Explain with risk management is it appropriate to know : What if you move forward with a risk you think is manageable but not mitigate it?

The difference between while loop and for loop in c language : Please explain the difference between while loop and for loop in C language with examples.

User Account

All Pages