I was working on a problem where we are supposed to give an example of an algorithm whose time complexity is O(n^2), but whose amortized time complexity is less than that. My immediate thought is nested loops, but I'm not exactly sure of what an example of that would look like where the result was amortized. Any insights would be greatly appreciated!
1 Answers
Consider the Add method on a Vector (resizable array) data structure. Once the current capacity of the array is exceeded, we must increase the capacity by making a larger array and copying stuff over. Typically, you'd just double the capacity in such cases, giving rise to a worst-case O(n) Add, but an O(1) amortized Add. Instead of doubling, we're of course free to increase it by squaring (provided the initial capacity is greater than one). This means that, every now and then, an add will take O(n^2) time; but such an increasingly large majority of them will take O(1) time that the amortized complexity will be O(1) as well.
Combining variations on this idea with the multiplicative effect on complexity of putting code into loops, it's probably possible to find an example where the worst-case time complexity is O(f) and the amortized complexity is O(g), for and f and g where g is O(f).
Related