The complexity of bubble sort and insertion sort for a list with a given number of inversions
<p>Let the length of a list be n, and the number of inversions be d. Why does insertion sort run in O(n+d) time and why does bubble sort not?</p>

<p>When I consider this problem I am thinking of the worst case scenario. Since the worse case for inversions is n(n-1)\2, both bubble and insertion sort run in the same time. But then I don't know how to answer the question since I find them the same. Can someone help me with this? </p>