Paradigms for complexity analysis of algorithms
There are natural variants of worst-case analysis that are also useful. Perhaps the most famous one is parametrized complexity. Here, we consider a "two-dimensional" measure: the usual input length $n$ and some additional non-negative integer $k$, the parameter. Even though an algorithm may run horribly in the worst case (for all values of $n$ and $k$), it could be that all the cases in one's application that needs to be solved, this parameter $k$ happens to be low, so the algorithm runs well on those instances.

For example, suppose you want to solve Maximum Independent Set on some class of graphs, and develop an interesting algorithm that is surprisingly fast. Investigating further into the class of graphs themselves, you find that all the graphs you examine just happen to have treewidth at most $10$. Well, Bodlaender (cf. Neidermeier [1]) showed that when the treewidth is k, Max Independent Set is fixed parameter tractable: it can be solved in $O(2^k (|E|+|V|))$ time. This gives some explanation as to why your algorithm works well.

[1] R. Niedermeier, Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 2006.