Insertion sort has a complexity similar to bubble sort. The basic difference with bubble sort is that the number of swapping is much lower than bubble sort. Here is the complexity for insertion sort:
|
Best time complexity |
Ω(n) |
|
Worst time complexity |
O(n2) |
|
Average time complexity |
Θ(n2) |
|
Space complexity (worst case) |
O(1) |