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
Which are the two standard ways of traversing a graph? i. The depth-first traversal   ii. The breadth-first traversal

Determine the Components of Illumination The light reaching the eye when looking at a surface has clearly come from a source (or sources) of illumination and bounced off the su

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

Mid Square method with good example


Write the algorithm for compound interest

A driver takes shortest possible route to attain destination. The problem which we will discuss here is similar to this type of finding shortest route in any specific graph. The gr

Prim's algorithm employs the concept of sets. Rather than processing the graph by sorted order of edges, this algorithm processes the edges within the graph randomly by building up

The complexity of searching an element from a set of n elements using Binary search algorithm is   O(log n)

The smallest element of an array's index is called its Lower bound.