4 ms·

What the heck is a "Quicksort big-O score"? I've never heard anyone use the noun score when talking about complexity analysis.

• JorgeGT 10y ago
  "Order" would be the commonly used term, right? At least in my native language.
• protomyth 10y ago
  I assume they want the average O(n log n), but who the heck knows given the script from above. I get the feeling this: http://bigocheatsheet.com http://bigocheatsheet.com would come in handy
  • steven777400 10y ago
    Big-O technically means "worst case", which for Quicksort is O(n^2), although usually (in normal cases) it runs better than that. Other sort algorithms can guarantee not worse than O(n log n).
    • protomyth 10y ago
      Must have been a while, I thought you went with average, but I guess its been 20 years. I mostly lived in optimizing cache since college.
    • susi22 10y ago
      That's incorrect. The /mathematical/ definition means that it's the upper bound. I.e. yes, the set of all functions of O(N) is a subset of the set of all functions O(N^2). So you could say Quicksort is O(N^100) and still be technically correct. However, the big-O notation does NOT specify anything about worst/avg/best-case complexity of a given algorithm. That should still be defined in the analysis. You mixed up those two slightly different concepts.
    • TimonKnigge 10y ago
      Depending on how the pivot is picked, Quicksort can actually be implemented in O(n lg n) worst-case time. EDIT: I was going to link a proof for this but it's surprisingly hard to find. IIRC, the idea is to use the median of medians algorithm ([1]) to pick the median for the pivot, and deal with values equal to the pivot by alternatingly placing them in the left and right partition, or alternatively just keep them in a third partition in the middle. [1] https://en.wikipedia.org/wiki/Median_of_medians https://en.wikipedia.org/wiki/Median_of_medians