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
what is hashing? what are diffrent method of hashing?

Objectives The purpose of this project is to give you significant exposure to Binary Search Trees (BST), tree traversals, and recursive code. Background An arbitrary BST i

Which sorting algorithms does not have a worst case running time of  O (n 2 ) ? Merge sort

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Define a B-Tree Justas AVL trees are balanced binary search trees, B-trees are balanced M-way search trees. A B-Tree of order M is either the empty tree or it is an M-way searc

Ruby implementation of the Symbol ADT Ruby implementation of the Symbol ADT, as mentioned, hinges on making Symbol class instances immutable that corresponds to the relative la

Two broad classes of collision resolution techniques are A) open addressing and B) chaining

Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?             A n s . H as h Table is explained as follows : A hash table is a data struc