Scribd
Upload
8 views10 pages

QuickSort Time Complexity Analysis

The document outlines the steps for analyzing time complexity, specifically for the QuickSort algorithm. It details identifying the basic operations, counting their occurrences, forming a recurrence relation, and solving it to determine that QuickSort has a time complexity of O(n log n). The analysis confirms that QuickSort operates in linearithmic time in both best and average cases.

Uploaded by

522Niya Joshy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views10 pages

QuickSort Time Complexity Analysis

The document outlines the steps for analyzing time complexity, specifically for the QuickSort algorithm. It details identifying the basic operations, counting their occurrences, forming a recurrence relation, and solving it to determine that QuickSort has a time complexity of O(n log n). The analysis confirms that QuickSort operates in linearithmic time in both best and average cases.

Uploaded by

522Niya Joshy
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Time Complexity Analysis Steps

•Identify the basic operation.

•Count how many times it runs (depends on input size).

•Set up a recurrence relation if recursive.

•Solve the recurrence

•Consider best, average, and worst cases.

•Present the final time complexity.


Analysis of quick sort
[Link] the Basic Operation
Determine the operation that dominates the
execution time.
For QuickSort, the key operations are:
•Choosing a pivot
•Partitioning
•Recursive calls
2. Count the Number of Basic Operations

1. Partitioning takes n times.

2. Two recursive calls are made on subarrays of size ≈

n/2
3. Form a Recurrence Relation
Create a recurrence based on how the algorithm breaks the
problem down.

T(n)=2T(n/2)+cn

•T(n) is the time to sort n elements,

•cn is the time taken to partition the array

•c is a constant.
Solve the recurrence (using Sunstituion method)
We expand T(n) by repeatedly substituting the recursive terms

First expansion: T(n)=2T(n/2)+cn (n = n/2)


Second expansion :
= 2(2T(n/4)+c(n/2))+cn
=4T(n/4)+cn+cn
=4T(n/4)+2cn
Third Expansion : 4(2T(n/8)+c(n/4))+2cn
=8T(n/8)+cn+cn+cn
= 8T(n/8)+3cn

After k expansions : T(n)=2k T(n/2k)+kcn


Solve for base case
We reach the base case when:
n/2k=1⇒2k=n⇒k=log2​n
Substitute K back in T(n)=2k T(n/2k)+kcn
T(n)=2log2​n⋅ T(1)+cn⋅ log2​n
=n⋅ T(1)+cnlogn

Assume T(1) = c₀ (a constant),


so:T(n)=n⋅ c0+cnlog⁡n
=O(nlog⁡n)
• Final Result:
Time Complexity T(n)=O(nlog⁡n)​
• This confirms that in the best and average
cases, QuickSort runs in linearithmic time.

You might also like