0

I was asked this question:

Which of these sorting algorithms have a worst-case running time of Ω(n2) — Bubble Sort, Heap Sort, Insertion Sort, Merge Sort, Quick Sort (with good median finding), Selection Sort.

Can someone explain what needs to be done?

Jay Patel
  • 1,266
  • 6
  • 20
  • 38
  • What exactly do you want to know? What the omega notation means? How the algorithms work? How to calculate their time complexity? – vesan Oct 02 '15 at 06:08
  • What is meant by worst case running time of Omega n^2 – Jay Patel Oct 02 '15 at 06:09
  • 1
    Worst case is denoted by BigOh right? So why Omega is used? – Jay Patel Oct 02 '15 at 06:10
  • 2
    You're confusing 2 different things. Worst-case running time of an algorithm means that the data is arranged in such a way that the algorithm takes the longest possible time for that data size. See [this](https://en.wikipedia.org/wiki/Worst-case_complexity) Wikipedia article. The big omega notation represents a relationship between data size and the time the algorithm takes. Answers to this question explain that: http://stackoverflow.com/questions/471199/what-is-the-difference-between-%ce%98n-and-on – vesan Oct 02 '15 at 06:18
  • @vesan you mean this? http://stackoverflow.com/a/471470/2431281 – Keale Oct 02 '15 at 06:20
  • 1
    @Keale Yes, that's a good short explanation. The top answer (http://stackoverflow.com/a/471206/2428407) has a more technical one. Or, if you're feeling even more technical, there's always Wikipedia: https://en.wikipedia.org/wiki/Big_O_notation#Big_Omega_notation – vesan Oct 02 '15 at 06:31
  • Then, the OP's question becomes confusing indeed. @JayPatel please add more details to your question. As it currently stands, it's hard to tell what you exactly want to know. – Keale Oct 02 '15 at 06:42
  • I also tried to explain that in: http://stackoverflow.com/a/12338937/572670 – amit Oct 02 '15 at 06:59
  • This is the same as asking which of the algorithms have an input that proves the O(n^2) running time is tight. – chepner Oct 02 '15 at 18:01
  • @Keale I meant, what is to be done to reach the answer. Find Omega of all sorting algorithm and pick worst among all of them ? – Jay Patel Oct 02 '15 at 18:24

1 Answers1

0

Simply put it, the type of analysis and the notation are seperate terms. You can apply each of big-O,little-o,big-Omga,little-omega, big theta and more (like tilde notations) to any of the analysis (including: best case, worst case, average case).

You have the type of analysis. This gives you the complexity function, like for example for merge sort's worst case:

T(n) = 2T(n/2) + CONST*n + SOME_CONSTANT

Then, you can analyse this T(n) and derive some conclusions. The asymptotic notations are set of functions, or "family" of functions that have common asymptotic behavior. For the above examples, you can conclude:

  • This function is in Theta(nlogn)
  • This function is in O(nlogn)
  • This function is in Omega(1)
  • This function is in O(n^3)
amit
  • 175,853
  • 27
  • 231
  • 333