Estimate the time complexity of Quick-sort Algorithm (Worst and Best) ?
To estimate the time complexity of Quick-sort Algorithm using the Master Theorem, we need to first
express the recurrence relation for the algorithm.
Recurrence Relation for Quick-sort Algorithm
In Quick-sort, we pick a pivot and partition the array into two sub-arrays. The time taken to partition the
array is linear, i.e., O(n), and then we recursively apply the Quick-sort algorithm to the two subarrays.
The recurrence relation for Quick-sort can be written as:
T(n) = aT (n/b) + O(n)
where:
T(n) is the time complexity for sorting an array of size (n)
(a) is the number of recursive calls partition into two subarrays
(b) is the factor by which the problem size is reduced at each step splitting into two subarrays
O(n) represents the linear time it takes to partition the array
Thus, for Quick-sort Algorithm:
T(n) = 2T (n/2) + O(n)
This recurrence relation describes the running time of Quick-sort Algorithm in general. Now, we can
apply the Master Theorem to solve this recurrence relation.
Master Theorem Method:
The Master Theorem deals with recurrences of the form:
T(n) = aT (n/b) + O(n^d)
where:
(a) is the number of subproblems,
(n/b) is the size of each subproblem,
O(n^d) is the cost outside of the recursive calls (e.g., partitioning time).
To apply the Master Theorem, we need to compare (n^d) with ( n^log_b (a) ).Depending on the
comparison between (d) and ( log_b (a) ), we have three cases:
1. Case 1: If ( d < log_b (a) ), then T(n) = O(n^log_b(a) )
2. Case 2: If (d = log_b (a) ), then T(n) = O ( (n^d) log (n) )
3. Case 3: If ( d > log_b (a) ), then T(n) = O (n^d)
Step 1: Applying the Master Theorem to Quick-sort. For Quick-sort, our recurrence relation is:
T(n) = 2T(n/2) + O(n)
We can identify the parameters as follows:
a = 2 (since we are making 2 recursive calls),
b = 2 (because we are splitting the array into two),
d = 1 (since partitioning takes linear time, O(n).
Now, we compute ( log_b (a) ):
log_b (a) = log_2 (2) = 1
Step 2: Compare (d) with ( log_b (a) )
d=1
log_b (a) = 1
Since ( d = log_b (a) ), this falls under Case 2 of the Master Theorem Method.
Step 3: Time Complexity for Quick-sort (Best and Average Case)
According to case 2 of the Master Theorem, if ( d = log_b (a) ), the time complexity is:
T(n) = O ( (n^d) log (n) ) = O (n log (n) )
Thus, in the best case and the average case (where the pivot divides the array into two roughly equal
halves), the time complexity of Quick-sort is:
T(n) = O (n log (n) )
Step 4: Time Complexity for Quick-sort Algorithm (Worst Case)
In the worst case, the array is not split evenly. For example, if the pivot always ends up being the
smallest or largest element (i.e., one subarray has size (n-1) and the other has size 0), the recurrence
becomes:
T(n) = T (n-1) + O(n)
This recurrence describes an unbalanced division where one of the subarrays has nearly all the elements.
This results in:
T(n) = T (n-1) + n
Solving this recurrence gives:
T(n) = O (n^2)
In this case, Quick-sort degrades to quadratic time, O(n^2)
Using the Master Theorem Method, we can estimate the time complexity of Quick-sort Algorithm as:
- Best Case: O (n log (n) )
- Average Case: O ( n log (n) )
- Worst Case: O (n^2)