2 ms·
> Insertion sort is O(n^2) on the number of comparison operations, because this step is O(n) on the number of sorted items Locating the correct position in the
by thaumasiotes 6y ago
> Insertion sort is O(n^2) on the number of comparison operations, because this step is O(n) on the number of sorted items
Locating the correct position in the sorted items is O(log n) on the number of sorted items. You point this out yourself later in your comment. Because the sorted items are sorted, it's not necessary to examine each of them.
Doing O(log i) work as i varies from 1 to n is O(log n!) work, which is O(n log n); not much different from doing O(log n) work as i varies from 1 to n.
I'm not sure how to interpret the two halves of this quote. It looks to me like I'm doing O(n log n) comparisons, and also finishing the sort in O(n log n) work overall. I'm not taking O(n^2 log n log n) work to finish the sort.
- Zelizz 6y ago> Because the sorted items are sorted, it's not necessary to examine each of them. This is true, but I'm being pedantic and calling the quadratic form of insertion sort just "insertion sort", and the form that does a binary search on the sorted items "binary insertion sort". https://en.wikipedia.org/wiki/Binary_insertion_sort https://en.wikipedia.org/wiki/Binary_insertion_sort