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
Q. Assume that we have separated n elements in to m sorted lists. Explain how to generate a single sorted list of all n elements in time O (n log m )?

What is Class invariants assertion A class invariant is an assertion which should be true of any class instance before and after calls of its exported operations. Generally


Q. Give the algorithm to build a binary tree where the yields of preorder and post order traversal are given to us.

Determine about the logic gates Many electronic circuits operate using binary logic gates. Logic gates essentially process signals that represent true or false or equivalent i.

A Stack has an ordered list of elements & an array is also utilized to store ordered list of elements. Therefore, it would be very simple to manage a stack by using an array. Thoug

differences between direct and indirect recursion

Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

Acyclic Graphs In a directed graph a path is said to form a cycle is there exists a path (A,B,C,.....P) such that A = P. A graph is called acyclic graph if there is no cycle in

Programming for hash table?