What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?a)Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)b)Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)c)Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)d)Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)Correct answer is option 'B'. Can you explain this answer?

Question

Answer

Recurrence and Time Complexity of QuickSort

Recurrence relation for QuickSort:
● QuickSort is a divide-and-conquer algorithm that partitions an array around a pivot element and recursively sorts the sub-arrays on either side of the pivot.
● In the worst case, the pivot element is either the smallest or largest element in the array, which leads to the partitioning of the array into two sub-arrays of size n-1 and 0 respectively.
● Therefore, the recurrence relation for QuickSort in the worst case is T(n) = T(n-1) + O(n) because we need to sort the sub-array of size n-1 and partition the array of size n in O(n) time.

Time complexity of QuickSort:
● To solve the recurrence relation, we can use the Master Theorem, which states that if a recurrence relation is of the form T(n) = aT(n/b) + f(n), then its time complexity is O(n^logb(a)) if f(n) = O(n^c) for some constant c < logb(a),='' and='' o(n^clogb(a))='' if='' f(n)='' />
● In the worst case of QuickSort, a = 1, b = n, and f(n) = O(n), so we have logb(a) = 0 and c = 1.
● Therefore, the time complexity of QuickSort in the worst case is O(n^clogb(a)) = O(n^1logn) = O(nlogn).

Conclusion:
The correct option is B, where the recurrence relation is T(n) = T(n-1) + O(n) and the time complexity in the worst case is O(nlogn).

Answer

The worst case of QuickSort occurs when the picked pivot is always one of the corner elements in sorted array. In worst case, QuickSort recursively calls one subproblem with size 0 and other subproblem with size (n-1). So recurrence is T(n) = T(n-1) + T(0) + O(n) The above expression can be rewritten as T(n) = T(n-1) + O(n) void exchange(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } int partition(int arr[], int si, int ei) { int x = arr[ei]; int i = (si - 1); int j; for (j = si; j <= ei - 1; j++) { if(arr[j] <= x) { i++; exchange(&arr[i], &arr[j]); } } exchange (&arr[i + 1], &arr[ei]); return (i + 1); } /* Implementation of Quick Sort arr[] --> Array to be sorted si --> Starting index ei --> Ending index */ void quickSort(int arr[], int si, int ei) { int pi; /* Partitioning index */ if(si < ei) { pi = partition(arr, si, ei); quickSort(arr, si, pi - 1); quickSort(arr, pi + 1, ei); }

Similar Computer Science Engineering (CSE) Doubts

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n( 2) numbers? In the recurrence equations given in the options below, c is a constant.

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company