Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing in each step, while average analysis produces an expected cost based on probabilities.
For them to both exist as separate ways of doing analysis of algorithms, then one must be preferred over the other one in some cases, however I can't figure a case to actually show that.
The two are not mutually exclusive. In most situations you're interested in amortized analysis, since usually operations are fast enough so that no user would notice a one time long running time, the real performance being determined by the amortized running time. A good example is garbage collection, essential to many modern computer languages. Garbage collection is extremely slow, but the cost is amortized to be very manageable.
The only notable exception to this is real time applications. For example, if you're operating a hard drive, you need to be fast always. Same goes for some other services provided by the operating system. But that's a specialized area.
Average case analysis is relevant when you can expect the data to be random enough. For example, a long scientific simulation could include a random element, and can be analyzed accordingly. Other data should not be assumed to be random for security reasons. For example, a web server distributing work across other servers can be attacked if load balancing relies only on input randomness.
Sometimes the average case is hard to define. For example, the simplex algorithm and SAT solvers often seen to run much faster than the worst case, but it's hard to attribute this to average case behavior since it's difficult to come up with a relevant average case distribution. Instead, one could point out some relevant features of the input, but doing this rigorously is very hard.
