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

Question

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

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

Answer 1

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-3)) + \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$.

• Magnetic Kode: So since (n(n-1))/2 is a valid quadratic equation, the time complexity is O(n^2)?
• Yuval Filmus: 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)$.