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?
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?
For bubble sort, if the last element needs to get to the first position (n inversions) you need to loop over the entire array n times, each time moving the element one position forward so you get n^2 steps, so you get O(N^2) regardless of the value of d.
The same setup in insertion sort will do only n+n steps to get everything sorted (O(N+d)). d is actually the total number of swaps insertion sort will need to do to get the thing sorted.
You went wrong when you assumed the worst case value of d is n(n-1)/2. While this is true, if you want to express the complexity in terms of d you can't replace it with it's worst value case, unless you're ok with a higher bound.