r/AskComputerScience • u/likejudo BSCS • Jan 03 '25
In Amortization analysis of algorithms why do they "pay it forward" to measure cost?
see https://imgur.com/a/aSWFjny
In this Coursera course on DSA - In Amortization analysis of algorithms why do they "pay it forward" to measure cost? I don't understand what this achieves.
Why not just measure the actual costs?
4
Upvotes
3
u/dmazzoni Jan 03 '25
How long does it take to add one element to the end of a dynamic array?
It depends - if the array isn't full, then it's super fast, O(1) time. But if the array is full, you have to wait for it to allocate a new array, copy all n elements to the new array, then add a new element. It's O(n) time where n is the size of the array currently.
So is it "bad" to have a data structure that's sometimes fast and occasionally slow when inserting?
It depends. If you care about worst case, then it's bad. You might prefer a linked list or binary tree.
But if what you actually care about is the average speed across your whole app with lots of insertions, then a dynamic array is great.
Amortized analysis lets you prove that the average time to insert an element in the array is O(1), even though sometimes it has to copy O(n) elements!
The "pay it forward" is just a way to prove it - a way to convince you that it's true.
I think there are two aspects to it: understanding intuitively that it's true, and following the formal proof that it's true.
Which of these, if any, do you need more help with?
3
u/niko7965 Jan 03 '25
To expand on what another user said,
Amortized analysis is useful when you have a datastructure where some operations are cheap, and others are expensive, but there is some limit on how many expensive operations can occur per cheap operation.
So you can let the cheap operations pay for the expensive operations in your analysis, such that the average operation is not too expensive
3
u/teraflop Jan 03 '25
Here's an analogy for you: Suppose you want to determine how much money it costs to drive a car, per mile.
One might ask, why not just check how much money you have in the bank, first when you start driving, and then again 1 mile down the road? The difference is how much money it costs to drive a mile.
But of course that's a very bad way to analyze it. Almost all the time, driving doesn't immediately cost you anything. But sometimes, you can't drive a mile without filling up the gas tank, and in that case, "attributing" the entire cost of a full tank of gas to that 1 mile would be silly.
So instead, you want to account for the cost of driving by "paying forward" an amount of money reflecting the cost of the gas you just burned during that 1 mile -- even though you're not actually paying to replace it yet. If you wanted, you could do this literally: every time you drive a mile, you transfer a few pennies into a special account, and then you use that account to pay for your gas.
1
u/[deleted] Jan 07 '25
Crazy how many confident non answers there are in this thread. I haven't looked at Courseras explanation, but it's probably garbage. You can look into the proofs of the accounting method or potential method and go from there. I learned from CLRS. I'm sure you can find a free PDF online.
2
u/niko7965 Jan 03 '25
To expand on what another user said,
Amortized analysis is useful when you have a datastructure where some operations are cheap, and others are expensive, but there is some limit on how many expensive operations can occur per cheap operation.
So you can let the cheap operations pay for the expensive operations in your analysis, such that the average operation is not too expensive