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. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

Ask question find frequency count of function- {for(i=1;i {for(j=1;j {for(k=1;k } } }

Game trees An interesting application of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can picture the sequence of possible moves by m

Taking a suitable example explains how a general tree can be shown as a Binary Tree. Conversion of general trees to binary trees: A general tree can be changed into an equiv

Initially Nodes are inserted in an AVL tree in the same manner as an ordinary binary search tree. Though, the insertion algorithm for any AVL tree travels back along with the pa

In the array implementation of lists, elements are stored into continuous locations. In order to add an element into the list at the end, we can insert it without any problem. But,

Channel access In first generation systems, every cell supports a number of channels. At any given time a channel is allocated to only one user. Second generation systems also

Program segment for All pairs shortest paths algorithm AllPairsShortestPaths(int N, Matrix C, Matrix P, Matrix D) { int i, j, k if i = j then C[i][j] = 0  for ( i =

Question 1 Discuss the following theorems with respect to Splay Trees- Balance Theorem Dynamic Finger Theorem   Question 2 Write a C program for implementation