Question

In: Computer Science

(a) Consider the general k-ary search algorithm (generalization of binary search) which splits a sorted array...

(a) Consider the general k-ary search algorithm (generalization of binary search) which splits a sorted array of size n into k subsets each of size n/k and recursively searches only one of these k subsets. Which one of these k subsets should be searched is decided by making (k − 1) comparisons, each of which can be done in constant time. Clearly, the recurrence relation for this k-ary search algorithm can be written as,

T(n) = T(n/k) + (k − 1)

Since k is a variable in the above recurrence relation, as an algorithm designer, you have the flexibility to set the value of k. Suppose you set k = n 2/3 . Analyze running time of the resulting algorithm in Θ notation.

(b) Show that f(n) = 2n 2 + 5n+ 3 is O(n 2 ) by finding adequate constants c and n0 where f(n) ≤ cn2 for all n ≥ n0.

Solutions

Expert Solution

Dear Student

In generalized k-ary search algorithm if the size of partition is more than one the time complexity will be logrithmic but if you put k =1 or less than 1( Which is not practically possible) the algorithm becomes linear and looses the sub-linearity propoerty,

venereology answered 1 year ago
Next > < Previous

Related Solutions

Consider the recursive formulation of the Binary Search algorithm. Given a sorted and non-decreasing list of...
Consider the recursive formulation of the Binary Search algorithm. Given a sorted and non-decreasing list of comparable objects L, and a new item x, find the location (index) of x or indicated that x is not in L. 5a) Give a recursive algorithm for binary search. No, while, for, repeat etc statements are allowed. Only if, if else and assignment statements are allowed. 5b) Write a difference equation for the running time of your Binary Search algorithm. Solve your equation...
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method...
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method could be public int BinarySearch(int target, int low, int high)
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method...
Write a recursive method to implement Binary Search of a sorted integer array. Signature of method could be public int BinarySearch(int target, int low, int high)
// This program demonstrates a Binary Search, which search for a value // in an array,...
// This program demonstrates a Binary Search, which search for a value // in an array, assuming that the array is sorted in descending order. // You have to modify the function binarySearch() to search for a value // in an array that is sorted in ascending order. // NOTES: // Uncomment line 34 and comment line 32. You don't have to edit anything // else in the main(), just in the binarySearch() function. // EXAMPLES (using the array sorted...
Binary Search Algorithm a.) Create a Java application that utilizes the "Binary Search Algorithm" presented in...
Binary Search Algorithm a.) Create a Java application that utilizes the "Binary Search Algorithm" presented in chapter 19 (NOT Java's pre-built binarySearch() method from imported Java library) to search for an integer in a random array of size 30 in the range of 0 to 1000 inclusive. You should use Java's random number generator to randomize the numbers in your array. b.) The application's main() method should display unsorted array and sorted array, prompt user for a search key, allow...
Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum...
Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. 42 39 2 6 9 16 20 28 31 34
Binary search for K=12 in the array A={2, 3, 5, 7,11,15, 16,18,19}
Binary search for K=12 in the array A={2, 3, 5, 7,11,15, 16,18,19}
Q2 - 15 pts) Given a minimum unimodal array of integers, run the binary search algorithm...
Q2 - 15 pts) Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. 0 1 2 3 4 5 6 7 8 9 33 32 27 26 24 22 21 8 7 3 IN C++ PLEASE
Q2 - 15 pts) Given a minimum unimodal array of integers, run the binary search algorithm...
Q2 - 15 pts) Given a minimum unimodal array of integers, run the binary search algorithm to find the minimum element. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. 0 1 2 3 4 5 6 7 8 9 33 32 27 26 24 22 21 8 7 3
Binary Search. Write a MIPS assembly program to perform a binary search on A[10], which is an array of 10 positive integers.
Binary Search. Write a MIPS assembly program to perform a binary search on A[10], which is an array of 10 positive integers. Your program should have a main routine that does the following:(a) Prompt the user to enter all the 10 integers in the array.(b) Prompt the user to enter the number to be searched.(c) Reads the integer values and makes sure it is a positive integer.(d) Prints the index of the integer. If the input is not available in...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT