DEV Community

loading...

Discussion on: Insertion Sort Quick Reference

Collapse
theodesp profile image
Theofanis Despoudis

O(n · log n) is not entirely correct as if you are counting comparisons then yes it's O(n · log n) but if you want to insert an element in the middle of the array you have to shift all the items right by one. Thus it can cost as much as n so the total cost can be:
O(n2)

Collapse
mortoray profile image
edA‑qa mort‑ora‑y Author

I state that in the Time: Copies section.