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

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

Give example of assertion and abstract data type For illustration, consider Natural ADT whose carrier set is the set of non-negative integers and whose operations are the usual

ST AC K is explained as follows : A stack is one of the most usually used data structure. A stack is also called a Last-In-First-Out (LIFO) system, is a linear list in

Q. Let a binary tree 'T' be in memory. Write a procedure to delete all terminal nodes of the tree.       A n s . fun ction to Delete Terminal Nodes from Binary Tree

what is far and near procedures in system programming?


In what ways we can get the context sensitive F1 help on a field?' Data element documentation. Data element additional text in screen painter. Using the process on help r

A linked list can be of the following types:-  Linear linked list or one way list Doubly linked list or two way list. Circular linked list Header linked list

Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)