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

ALGORITHM AND TRACING, WRITE AN ALGORITHM TO CONVERT PARENTHIZED INFIX TO P... WRITE AN ALGORITHM TO CONVERT PARENTHIZED INFIX TO POSTFIX FORM ALSO TRACE ALG ON ((A+B)*C-(D-E)$F+G)

Four applications or implementation of the stack, Q. Write down any four ap... Q. Write down any four applications or implementation of the stack.                                     Ans. (i)       The Conversion of infix to postfix form (ii)

Define a b-tree, Define a B-Tree Justas AVL trees are balanced binary s... 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

BINARY SEARCH, GIVE TRACE OF BINARY SEARCH ALGORITHM BY USING A SUITABLE EX... GIVE TRACE OF BINARY SEARCH ALGORITHM BY USING A SUITABLE EXAMPLE.

Non-recursive algorithm, Q .  Write down the non-recursive algorithm to tra... Q .  Write down the non-recursive algorithm to traverse a tree in preorder. Ans: T he Non- Recursive algorithm for preorder traversal is written below: Initially i

Explain in detail about the ruby arrays, Explain in detail about the Ruby a... Explain in detail about the Ruby arrays Ruby arrays have many interesting and powerful methods. Besides indexing operations which go well beyond those discussed above, arrays h

Difference between array and abstract data types, Difference between array ... Difference between array and abstract data types Arrays aren't abstract data types since their arrangement in the physical memory of a computer is an essential feature of their

Algorithm and flow chart, algorithm and flow chart to find weather the give... algorithm and flow chart to find weather the given numbers are positive or negative or neutral

Depth first search, DEPTH FIRST SEARCH (DFS) The approach adopted into ... DEPTH FIRST SEARCH (DFS) The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisite

Determine about the unreachable code assertion, Determine about the unreach... 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