Q. What do you mean by the best case complexity of quick sort and outline why it is so. How would its worst case behaviour arise?                                                                                                 

Ans:

In the best case complexity, pivot is in the middle. To simplify the calculation, we assume that the two sub-files are both  exactly half  of the size of the original file, and although this gives a minor overestimate, this is except able because we are only interested in a Big-Oh answer.

T(n) = 2T(n/2) + cn

which yields

T(n) = cn log n + n = O(n log n)

In the worst case the pivot is the smallest element, all the time. Then i = 0 and if we ignore  T(0) = 1, which is not important, the recurrence is T(n) = T(n - 1) + cn, n > 1 which yields

Posted Date: 7/10/2012 6:34:58 AM | Location : United States

Ask an Expert

Related Discussions:- Complexity of quick sort, Assignment Help, Ask Question on Complexity of quick sort, Get Answer, Expert's Help, Complexity of quick sort Discussions

Write discussion on Complexity of quick sort
Your posts are moderated

Write your message here..

Related Questions

Properties of red- black tree, Any Binary search tree has to contain follow... Any Binary search tree has to contain following properties to be called as a red- black tree. 1. Each node of a tree must be either red or black. 2. The root node is always b

Hashing, what is hashing? what are diffrent method of hashing? what is hashing? what are diffrent method of hashing?

File organization, Define File organization''s and it''s types Define File organization''s and it''s types

Tree Traversal, If preorder traversal and post order traversal is given the... If preorder traversal and post order traversal is given then how to calculate the pre order traversal. Please illustrate step by step process

FIRST function in the compiler construction, I need a recursive algorithm t... I need a recursive algorithm to implement the FIRST function to any grammar

Data structures, I am looking for assignment help on the topic Data Structu... I am looking for assignment help on the topic Data Structures. It would be great if anyone help me.

Applications of borazole, Ask question #Minimum 1cepted# Ask question #Minimum 1cepted#

Multiple Queues in a single dimension array, Implement multiple queues in a... Implement multiple queues in a single dimensional array. Write algorithms for various queue operations for them.

Big o notation, This notation gives an upper bound for a function to within... This notation gives an upper bound for a function to within a constant factor. Given Figure illustrates the plot of f(n) = O(g(n)) depend on big O notation. We write f(n) = O(g(n))

Data structure, Ask question #Minimum 1Mark each of the following statement... Ask question #Minimum 1Mark each of the following statements as valid or invalid. If a statement is invalid, explain why. a. current ¼ list; b. temp->link->link ¼ NULL; c. trail->l