# Why does the insertion-sort algorithm have a quadratic instead of a quasi-linear time complexity?

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;
}
}

• I am not sure you understood insertion sort. I think your understanding of the algorithm is opposite to what it actually is. – xuq01 Jun 21 '18 at 14:28
• Care to elaborate? I'm lost here. – Magnetic Kode Jun 21 '18 at 14:31
• I updated the post with my implementation of insertion sort in JS, if I made a mistake there, please point it out. – Magnetic Kode Jun 21 '18 at 14:34
• 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. – xuq01 Jun 21 '18 at 16:15
• "How is this O(n^2) and not O(nlogn)? " -- the two are not exclusive. Use $\Theta$ to ask your real question. – Raphael Aug 21 '18 at 7:31

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$.
• 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)$. – Yuval Filmus Jun 21 '18 at 16:11