Amortized analysis
Amortized analysis is like counting your piggy bank money over time.
When you save some change, you don't just count it every day to see how much you have. Instead, you wait until you have saved up a good amount, and then divide that by the number of days you've been saving to figure out how much money you've saved each day.
In the same way, in computer science, sometimes we want to know how much time or memory a series of operations will take, but we can't just measure each one on its own. We need to look at them all together to figure out what the average cost is over time.
Like with your piggy bank, we "collect" a bunch of operations and then divide the total time or memory by the number of operations to get an average cost.
For example, let's say you have a long list of numbers and you want to search for a particular number in that list. If you use a linear search (going through the list one by one until you find the number), the time it takes to search could vary a lot depending on where in the list the number is.
But if you use a binary search (where you start in the middle of the list and keep dividing it in half until you find the number), the time it takes will be more consistent.
But still, the first search might take longer than the second if the number is near the beginning of the list, and the second search might take longer if the number is near the end of the list.
So, to figure out the average cost of a binary search over many searches, we can use amortized analysis. We consider the total time taken for many searches (say, a million), and then divide that by the number of searches to get an average.
In this way, we can get a more accurate idea of how much time a binary search takes, even though the time it takes for each individual search can vary.
When you save some change, you don't just count it every day to see how much you have. Instead, you wait until you have saved up a good amount, and then divide that by the number of days you've been saving to figure out how much money you've saved each day.
In the same way, in computer science, sometimes we want to know how much time or memory a series of operations will take, but we can't just measure each one on its own. We need to look at them all together to figure out what the average cost is over time.
Like with your piggy bank, we "collect" a bunch of operations and then divide the total time or memory by the number of operations to get an average cost.
For example, let's say you have a long list of numbers and you want to search for a particular number in that list. If you use a linear search (going through the list one by one until you find the number), the time it takes to search could vary a lot depending on where in the list the number is.
But if you use a binary search (where you start in the middle of the list and keep dividing it in half until you find the number), the time it takes will be more consistent.
But still, the first search might take longer than the second if the number is near the beginning of the list, and the second search might take longer if the number is near the end of the list.
So, to figure out the average cost of a binary search over many searches, we can use amortized analysis. We consider the total time taken for many searches (say, a million), and then divide that by the number of searches to get an average.
In this way, we can get a more accurate idea of how much time a binary search takes, even though the time it takes for each individual search can vary.