Typically when we talk about analysis of algorithms or data structures, we focus on the worst case analysis most of the time, and also on the amortized analysis in some cases (though I feel we should be talking more about the latter than the former, but that's the subject of another post). Worst-case analysis summarizes the performance profile of an algorithm by its worst performance on any input of a given size, implicitly advocating for the algorithm with the best-possible worst-case performance. Recently we have been seeing quite a bit of work done on the subject tacitly called Beyond the Worst Case Analysis of Algorithms. Almost all the literature that I see on this subject is being led by Prof. Tim Roughgarden. The worst case approach has obviously been the most popular modeling choice across ages. Yet it has been found that for many complex problems, the predictions of worst-case analysis are overly pessimistic. Also with today's modern CPU cache lines, worst-case analysis, straightforwardly applied, provides no useful insights about the performance of algorithms in the presence of cache misses and different cache replacement policies. In fact we now have a whole modeling area where cache oblivious algorithms are being developed as an alternative. Modern machine learning algorithms that use neural networks, powered by massive data sets and computational power, have achieved impressive levels of performance across a range of prediction tasks. This is a direct challenge to the convention of modeling algorithms using worst case analysis. Even sublinear data structures like bloom filters are being improved using the power of machine learning (Fast Partitioned Learned Bloom Filter - arxiv.org/abs/2306.02846). In this paper Beyond the Worst Case Analysis of Algorithms (arxiv.org/abs/2007.13241), Prof. Tim Roughgarden introduces the idea of such analysis, and points out several important computational problems, like linear programming, clustering, and online caching, where the worst-case analysis framework does not provide much helpful advice on how to solve the problem. How to address these drawbacks ? Here's an excerpt from the paper .. These drawbacks show the importance of alternatives to worst-case analysis, in the form of models that articulate properties of “relevant” inputs and algorithms that possess rigorous and meaningful algorithmic guarantees for inputs with these properties. Research in “beyond worst-case analysis” is a conversation between models and algorithms, with each informing the development of the other. For more details, there's a book edited by Prof Roughgarden (see pic) that goes into the depth of this subject addressing all the concerns and suggesting alternatives. Looks like a very good and emerging discipline in the analysis of algorithms ..