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

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

Ask an Expert

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

Write your message here..

Related Questions

Degree of node, Q. The degree of a node is defined as the number of childre... 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

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

Define game trees, Game trees An interesting application of trees is th... 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

Conversion of general trees to binary trees, Taking a suitable example expl... 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

Insertion of a node into an avl tree, Initially Nodes are inserted in an AV... 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

Insertion in list, In the array implementation of lists, elements are store... 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,

Process of channel access, Channel access In first generation systems, ... 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 for all pairs shortest paths algorithm, Program segment for All pai... 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 =

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

Entity relationship, what is cardinality what is cardinality