2
$\begingroup$

Can someone explain how the insertion sort have quadratic time complexity and not quasi-linear time complexity in the worst-case?

Even in the case of a reversely sorted list, it's not like it'll have to compare each element with all the other elements. For example in [4, 3, 2, 1], 4 won't be compared with anything. 3 will only be compared with 4. 2 will be compared with 4 and 3 but not 1. And only 1 will be compared with all the other 3 items.

How is this O(n^2) and not O(nlogn)? What am I missing here?

My implementation of Insertion Sort:

const insertionSort = (arr) => {
  for (let i of arr) {
    for (let x = arr.indexOf(i) - 1; x >= 0 && arr[x] > i; x--) {
      arr[x + 1] = arr[x];
      arr[x] = i;
    }
  }
$\endgroup$
  • 1
    $\begingroup$ I am not sure you understood insertion sort. I think your understanding of the algorithm is opposite to what it actually is. $\endgroup$ – xuq01 Jun 21 '18 at 14:28
  • $\begingroup$ Care to elaborate? I'm lost here. $\endgroup$ – Magnetic Kode Jun 21 '18 at 14:31
  • $\begingroup$ I updated the post with my implementation of insertion sort in JS, if I made a mistake there, please point it out. $\endgroup$ – Magnetic Kode Jun 21 '18 at 14:34
  • $\begingroup$ OK, I thought you were inserting in the opposite direction. Your analysis is mostly right. For why this is O(n^2) see Yuval's answer. $\endgroup$ – xuq01 Jun 21 '18 at 16:15
  • $\begingroup$ "How is this O(n^2) and not O(nlogn)? " -- the two are not exclusive. Use $\Theta$ to ask your real question. $\endgroup$ – Raphael Aug 21 '18 at 7:31
1
$\begingroup$

On an array of length $n$ which is reversely sorted, the first element would be compared to 0 elements, the second element to 1, the third element to 2, and so on. In total, the number of comparisons will be $$ 0 + 1 + 2 + \cdots + (n-1) = \\ \frac{1}{2} \bigl((0 + 1 + 2 + \cdots + (n-1)) + ((n-1) + \cdots + 2 + 1 + 0)\bigr) = \\ \frac{1}{2} \bigl((0 + (n-1)) + (1+(n-2)) + (2+(n-1)) + \cdots + ((n-1)+0)\bigr) = \\\ \frac{1}{2} \bigl(\underbrace{(n-1) + (n-1) + (n-1) + \cdots + (n-1)}_{\text{$n$ times}}\bigr) = \\ \frac{n(n-1)}{2}. $$ This number scales like $n^2$.

$\endgroup$
  • $\begingroup$ So since (n(n-1))/2 is a valid quadratic equation, the time complexity is O(n^2)? $\endgroup$ – Magnetic Kode Jun 21 '18 at 15:42
  • 2
    $\begingroup$ More importantly, the running time is also $\Omega(n^2)$, i.e., it is $\Theta(n^2)$. In particular, it is not $O(n\log n)$. $\endgroup$ – Yuval Filmus Jun 21 '18 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.