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?
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?
DPO simplifies: removes the explicit reward model, trains directly on preferences
DeFi removes intermediaries like banks
ACID
ACID guarantees data validity in transactions
eventual consistency means: all replicas converge to the same state given enough time
Ever wonder why your favorite online store always shows you the same price for a product, even if you see different prices elsewhere?
Swipe through 100 ML concepts daily
Open Pocket Polymath