The worst case of QuickSort occurs when the partition process always picks greatest or smallest element as pivot. If we consider a large array with n elements, the partition process will divide the array into two sub-arrays with 0 and n-1 elements. So, the recurrence for the worst case is:

T(n) = T(n-1) + Θ(n)

The above recurrence represents time complexity in the worst case and solving it we get the time complexity as Θ(n^2).

The Θ(n) is the time required to process the partition. Since in worst case, the partition process is performed n times (recursively), the time complexity in worst case becomes Θ(n^2).

Question

The worst case of QuickSort occurs when the partition process always picks greatest or smallest element as pivot. If we consider a large array with n elements, the partition process will divide the array into two sub-arrays with 0 and n-1 elements. So, the recurrence for the worst case is:

T(n) = T(n-1) + Θ(n)

The above recurrence represents time complexity in the worst case and solving it we get the time complexity as Θ(n^2).

The Θ(n) is the time required to process the partition. Since in worst case, the partition process is performed n times (recursively), the time complexity in worst case becomes Θ(n^2).

Knowee AI · Accepted Answer

The worst case of QuickSort occurs when the partition process always picks greatest or smallest element as pivot. If we consider a large array with n elements, the partition process will divide the array into two sub-arrays with 0 and n-1 elements. So, the recurrence for the worst case is:

T(n) = T(n-1) + Θ(n)

The above recurrence represents time complexity in the worst case and solving it we get the time complexity as Θ(n^2).

The Θ(n) is the time required to process the partition. Since in worst case, the partition process is performed n times (recursively), the time complexity in worst case becomes Θ(n^2).

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

Question

Solution

Similar Questions

Upgrade your grade with Knowee