Complexity of quick sort, Data Structure & Algorithms

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

1908_Quick Sort1.png

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







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
Related Questions
Illustrate the intervals in mathematics Carrier set of a Range of T is the set of all sets of values v ∈ T such that for some start value s ∈ T and end value e ∈ T, either s ≤

Q. Let a binary tree 'T' be in memory. Write a procedure to delete all terminal nodes of the tree.       A n s . fun ction to Delete Terminal Nodes from Binary Tree


Normal 0 false false false EN-IN X-NONE X-NONE MicrosoftInternetExplorer4

Explain principle of Optimality It indicates that an optimal solution to any instance of an optimization problem is composed of  optimal solutions to its subinstances.

How does cpu''s part tming and controls generate and controls signls in computer?


If a node in a BST has two children, then its inorder predecessor has No right child

Q. Using the following given inorder and preorder traversal reconstruct a binary tree Inorder sequence is D, G, B, H, E, A, F, I, C

In-order Traversal  This process when executed iteratively also needs a stack and a Boolean to prevent the implementation from traversing any portion of a tree twice. The gener