Medians and Order statistics
Not what you're looking for?
Please review problem and verify the solution.
problem
---------
In the algorithm SELECT, the input elements are divided into groups of 5. Will the algorithm work in linear time if they are divided into groups of 7? Argue that SELECT does not run in linear time if groups of 3 are used.
solution
---------
Use groups of k for the analysis. The worst case SELECT will be called recursively on at most n - (n/4 - k) = 3n/4 + k elements.
The recurrence is T(n) <= T(ceiling(n/k)) + T(3n/4 + k) + O(n)
Solve the recurrence by substitution
I believe the solution is the following:
T(n) <= T(ceiling(n/k)) + T(3n/4 + k) + O(n)
<= c(n/k + 1) + 3cn/k + c(k+1) + O(n)
<= cn(1/k + 3/4) + c(k + 1) + O(n) [ this only holds for k > 4 so we have proved it works for any group size of 4 or more]
<= cn
Purchase this Solution
Solution Summary
Medians and Order statistics are evaluated.
Purchase this Solution
Free BrainMass Quizzes
Basic Networking Questions
This quiz consists of some basic networking questions.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
C++ Operators
This quiz tests a student's knowledge about C++ operators.
Javscript Basics
Quiz on basics of javascript programming language.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.