Duda comparaciones InsertionSort

[rodrigooflores]

Hola! estaba haciendo las complejidades de los algoritmos otra vez y viendo la versión in-place del algoritmo InsertionSort me surgió una duda con la cantidad de comparaciones que se hacen.
Asumí que en la línea 3 while $(j>0)\land(A[j]<A[j-1])$ forzaba a que siempre se hicieran todas las comparaciones posibles independiente de si se hacían los intercambios o no, y por lo tanto la complejidad inicial (sin hacer análisis de inversiones) sería de $\mathcal{O}(n^2+k)$, pero en la diapositiva aparece que sería de $\mathcal{O}(n+k)$. Sé que para la complejidad de tiempo final esto no importa, pero igual me surge la duda, como está escrito el algoritmo ¿deberían hacerse $\frac{n(n-1)}{2}$ comparaciones o existe una forma de que solo sean $n$?
Gracias de antemano :)