Complexity of quick sort, Data Structure & Algorithms

Assignment Help:

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


Related Discussions:- Complexity of quick sort

Implementation of queue using a singly linked list, Implementation of queue...

Implementation of queue using a singly linked list: While implementing a queue as a single liked list, a queue q consists of a list and two pointers, q.front and q.rear.

Booth algorithm, what is boot algorithm and some example

what is boot algorithm and some example

Er diagram, Ask queConsider the following functional dependencies: Applican...

Ask queConsider the following functional dependencies: Applicant_ID -> Applicant_Name Applicant_ID -> Applicant_Address Position_ID -> Positoin_Title Position_ID -> Date_Position_O

Computational complexity, Generally, Computational complexity of algorithms...

Generally, Computational complexity of algorithms are referred to through space complexity (space needed for running program) and time complexity (time needed for running the progr

Java code and algorythem, Suppose that you want to develop a program that a...

Suppose that you want to develop a program that accepts a postfix expression and asks values for variables in the expression. Then you need to calculate the answer for the expressi

Write algorithm for post-order traversal, P os t - o r d e r T ...

P os t - o r d e r T r av er sal :  This can be done by both iteratively and recursively. The iterative solution would require a modification or alteration of the in-

Project, human resource management project work in c++

human resource management project work in c++

Frequency counts for all statements, Evaluate the frequency counts for all ...

Evaluate the frequency counts for all statements in the following given program segment. for (i=1; i ≤ n; i ++) for (j = 1; j ≤ i; j++) for (k =1; k ≤ j; k++) y ++;

An undirected graph g with n vertices and e edges, An undirected graph G wi...

An undirected graph G with n vertices and e edges is shown by adjacency list.  What is the time required to generate all the connected components? O (e+n)

Areas of use - sequential files, Sequential files are most frequently utili...

Sequential files are most frequently utilized in commercial batch oriented data processing where there is the concept of a master file on which details are inserted periodically. F

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd