# Sorting Quiz 1

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²)

B. Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n²)

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)

# Solution :

B) is correct.

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)

Below we can see the implementation of QuickSort :

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

--

--

--

## More from Placewit

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

## Placewit

Upskilling students for tech placements!