r/puremathematics • u/Wise_Shame_2052 • 12d ago
Amortized Analysis!
Can anyone explain me what is Amortized analysis, why it is used and diffrence of time complexity and amatorized! Then lastly suggest me a research paper or a article for better understand..... !.
1
Upvotes
3
u/apnorton 12d ago
The wikipedia page on this is excellent, and I'd recommend giving it a read, as well as some of its sources.
The short version is that amortized analysis is used to discuss the time complexity of a piece of code over multiple executions. You can think of it as an "average runtime" that doesn't depend on specific selections of inputs.
For example, suppose you had some function that you are going to call 2N+1 times. On the kth call of the function (starting counting at 0), if k is a power of 2 (i.e. k = 2i), then the function takes O(k) time. Otherwise, the function takes O(1) time. So, in total, the 2N calls of this piece of code take O(sum(2k, k=0 to N) + 2N-(N+1)) time --- the sum is adding up the N+1 calls that are powers of 2 and take linear time, while the 2N-(N+1) is the amount of time taken up by the constant calls. We may simplify this sum and we end up with the 2N calls taking O(2N - N) time. But, if you have 2N calls taking O(2N) time, then this "averages" out to O(1) time per call! In a handwavy sense, the "spikes" in time usage are limited enough that the average behavior is still constant.
The canonical example for amortized analysis is that of appending to an ArrayList, which follows exactly the math given above (and is fleshed out in more detail in the wiki page).