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 :

Thanks for Reading

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

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

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

Recommended from Medium

One restaurant that has always done it right is Bareburger. If you don’t live in

Controlling lights with Ikea Trådfri, Raspberry Pi and AWS

Laravel 8: Simple, Yet Powerful Alert Component

In the pursuit of expanding the horizons of learning, Unacademy introduces courses for Chess and…

Help! My Azure Site Performance Sucks! — Part 1

Import .CSV files into MariaDB

How I Became a Self-taught Frontend Developer in 6 Months — My Story

Reproducible Intelligent Pigging Data in R Language

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

1650. Lowest Common Ancestor of a Binary Tree III

[Leetcode] Backspace String Compare

Scattered Rice Coding Question

LeetCode 238 — Product of Array Except Self