and not an exponential speed-up (O(2^n) to O(n): exponential to linear)

Note that you can also have an exponential speed-up when going from O(n) (or O(n^2) or other polynomial complexities) to O(log n). Of course that didn’t happen in this case.