Why does a slow day at the bank not mean every transaction is slow?
Image: United States Federal Reserve Bank, Public domain, via Wikimedia Commons
amortized O(1) means
Why does a slow day at the bank not mean every transaction is slow?
Imagine you're at a bank where some transactions take forever, but most are quick. You want to know if the bank is efficient overall.
Amortized analysis looks at all transactions together, not just the slow ones. It averages the time spent, so a few slow transactions don't ruin the bank's efficiency.
Example
If you make 99 quick transactions and 1 slow one, the average time per transaction is less than if all 100 were slow.
Remember this
Amortized analysis helps us see that an expensive operation is rare enough to not affect the average performance.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
Outline of databases
Ever wonder how your online bank keeps your money safe during transactions?
DPO simplifies: removes the explicit reward model, trains directly on preferences
Ever wished your bank could be both secure and flexible?
Overdrawn at the Memory Bank
Overdrawn at the Memory Bank was shot on videotape due to budget constraints
merge sort: O(n log n) always
Ever wondered why sorting your music library takes ages?
Strength reduction
Why do computers sometimes get tired of doing the same math over and over?
ACID
ACID guarantees data validity in transactions
Swipe through 100 ML concepts daily
Open Pocket Polymath