CODEWITHSUNDEEP
time-complexitybig-oquicksort
user7826451
user7826451

Reputation:

Quicksort omega-notation

Best case for Quicksort is n log(n) but everyone uses Big-O notation to describe the best case as O(n log (n)). From my understanding of notations, Quicksort has Big-Omega(n log (n)) and O(n^2). Is this correct or am I misunderstanding Big-Omega notation?

Upvotes: 3

Views: 3394

Answers (2)

fgb
fgb

Reputation: 18559

Big-O and Big-Omega are ways of describing functions, not algorithms. Saying Quicksort is O(n^2) is ambiguous because you're not saying what property of the algorithm you're describing.

Algorithms can have best-case time complexities, and worst-case time complexities. These are the time complexities of the algorithm if the best or worst performing inputs are used for each input size.

This is different from Big-O, and Big-Omega which describe upper and lower bounds of a function.

The time-complexities are given as a function of the input size, which can have their own upper and lower bounds.

For example, if you knew the best-case wasn't any worse than nlogn, then you could say the best-case time complexity is O(nlogn). If you knew it was exactly nlogn then it would be more precise to say Theta(nlogn).

Upvotes: 2

Dan Sp.
Dan Sp.

Reputation: 1447

You have the details incorrect. Big-O is technically supposed to be worst case. QuickSort has an average case of O(n log n) and a worst case of O(n^2). Going by the technical definition, the correct Big-O of QuickSort is then n^2. But the chances of randomly getting that performance is practically zero (unless you run QuickSort on an already sorted list) so QuickSort is given the Big-O of n log n even though it is not technically correct.

Big-Omega on the other hand is technically defined as "Takes at least this long" so it is a lower bound. That means QuickSort has Big-Omega(n log n) and n^2 has nothing to to with QuickSort and Big-Omega.

Upvotes: 0

Related Questions