I feel like I have a vague understanding of what an amortized analysis is. From what I've noticed, it's the time if the action in consideration is done a large number of times (on a large data set?). I know it's in contrast to worst-case cost analysis but if anyone has any helpful ways to explain it and how to find amortized cost, that would be great.
You can think of amortized a little like "average", but there's a subtle difference.
Average involves a random process. Amortized does not.
So, for example, suppose you have a system where (1) 1/2 the times you do an operation, it takes 1 second and (2) all other times it takes 10 seconds.
Suppose this is just random -- as if the system just flips a coin every time you do the operation and, based on the coin flip, it decides to do the fast or slow version. Then the average cost is 1/2 * 1 + 1/2 * 10 = 5.5 seconds. But sometimes two operations in a row will both be fast or both be slow.
Now suppose you have a similar system, except that it always alternates between fast and slow. Then the "average" time is the same, but you can now guaranteed that two successive operations will take 11 seconds. Never more. Never less. So you have a guarantee on the total cost of a sequence of operations. This is the idea of amortized analysis.
In a B^e-tree, sometimes an insert is fast, sometimes its slow, and predicting whether it is fast or slow is complicated, and further depends on all the previously inserted values. However, it is not random. So we can guarantee that the total work to insert N items is at most O((N log_B N) / (e B^(1-e)). Again, this is guaranteed, not "usually" or "on average".
In order to convert this into a cost "per insert", we take the total cost and divide it by the number of operations. That's what we call the amortized cost. In that regard, it looks a little like taking an average, but keep in mind we have a stronger guarantee than simply an average cost analysis of a randomized system.
Best, Rob