3

What I seen: First I have read these two other SO post

  1. Why is Insertion sort better than Quick sort for small list of elements?

  2. Is there ever a good reason to use Insertion Sort?

But the answers on there are not specific enough for me.

From answers from these two post they mainly pointed out Merge Sort and Quick Sort can be slow because of the extra overhead from the recursive function calls. But I am wondering how the specific threshold 7 get set?

My Question:

I want to know why the cut off is around 7 elements where quadratic sorting algorithm like Insertion Sort is faster than O(nlogn) sorting algorithm like Quick Sort or Merge Sort.

  • Use insertion sort on small subarrays. Mergesort has too much overhead for tiny subarrays.
  • Cutoff to insertion sort for ~ 7 elements.

I got this from Princeton lecture slide which I think is reputable enough source. see on the 11th slide under Mergesort: Practical Improvements section.

I will really appreciate it if your answer includes examples for mathematical proof.

OLIVER.KOO
  • 5,654
  • 3
  • 30
  • 62
  • 4
    The key thing to remember here is that Big-O is how the algorithm scales, not how fast it is. – Strikegently Dec 22 '17 at 18:08
  • Possible duplicate of [Why is Insertion Sort faster than Quick Sort when the input size is small?](https://stackoverflow.com/questions/19617790/why-is-insertion-sort-faster-than-quick-sort-when-the-input-size-is-small) – Jim Mischel Dec 22 '17 at 20:01
  • @JimMischel the SO post you provided talked about the concept. Here I am wondering specifically how the threshold of 7 is set. – OLIVER.KOO Dec 22 '17 at 20:09
  • 1
    Read the last paragraph of that answer. The number could be more or less than 7, depending on the operating environment. The only way to know for sure with any particular computer is to experiment. 7 is a good estimate, based on empirical results, and comparison of the constant factors in both algorithms. – Jim Mischel Dec 22 '17 at 20:19
  • alright, I am convinced. That is a great answer that you wrote Jim and it is what I am looking for. Should I linked your answer and then close my question? I am wondering why that post total vote is negative. – OLIVER.KOO Dec 22 '17 at 20:57
  • The question has a -1 score, probably because people thought the question itself was not asked well. 4 people thought it was a good question, and 5 people thought it was not. You can get the vote totals by clicking on the number, between the up and down arrows. – Jim Mischel Dec 22 '17 at 23:25
  • since the question was not asked well and the OP @lsbbo last seen was over half a year ago so I probably can't get the OP to edit the question. Would you mind migrate your awesome answer to this thread instead and I will accept it as an answer? – OLIVER.KOO Dec 22 '17 at 23:36

1 Answers1

3

Big-O only notes the factor that dominates as n gets large. It ignores constant factors and lesser terms, which pretty much always exist and are more significant when n is small. As a consequence, Big-O is near useless for comparing algorithms that will only ever need to work on tiny inputs.

For example, you can have an O(n log n) function with a time graph like t = 5n log n + 2n + 3, and an O(n^2) function whose time graph was like t = 0.5n^2 + n + 2.

Compare those two graphs, and you'll find that in spite of Big-O, the O(n^2) function would be slightly faster until n reaches about 13.

cHao
  • 84,970
  • 20
  • 145
  • 172
  • In Big-O notation, we can say, `O(n^2)`, grows faster than `O(n log n)`. If we plot these for n Eventually `O(n^2)` can overcome `O(n log n)` in specific value for n. [You can see Chart](http://bigocheatsheet.com/) – EsmaeelE Feb 23 '18 at 11:46