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. Which sorting algorithm can be easily adaptable for singly linked lists? Explain your answer as well.        Ans: The simple Insertion sort is sim

how to creat atm project by using linked list?

Determine about the unreachable code assertion An unreachable code assertion is an assertion that is placed at a point in a program that shouldn't be executed under any circum

Q. Explain various graph traversal schemes and write their advantages and disadvantages. A n s . Graph Traversal Scheme is explained below In many troubles we wish

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Merge sort is a sorting algorithm which uses the basic idea of divide and conquers. This algorithm initially divides the array into two halves, sorts them separately and then merge

Thus far, we have been considering sorting depend on single keys. However, in real life applications, we may desire to sort the data on several keys. The simplest instance is that

One of the best known methods for external sorting on tapes is the polyphase sort. Principle: The basic strategy of this sort is to distribute ordered initial runs of predetermi

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo