Other kinds of running time analysis besides worst-case, average-case, etc? Here are some ways to analyze the running time of an algorithm:

1) Worst-case analysis: Running time on the worst instance.

2) Average-case analysis: Expected running time on a random instance.

3) Amortized analysis: Average running time on the worst sequence of instances.

4) Smoothed analysis: Expected running time on the worst randomly perturbed instance.

5) Generic-case analysis: Running time on the worst of all but a small subset of instances.

My question: Is this a complete list?
I have two more for the list, which are somewhat similar.


Parameterized Analysis expresses the running time as a function of two values instead of one, using some additional information about the input measured in what's called the ``parameter''. As an example take the Independent Set problem. The best running time for the general case is of the form $O(c^n n^{O(1)})$ for some constant $1 &lt; c &lt; 2$. If we now take as parameter the treewidth of the graph and represent it by the parameter $k$, an Independent Set can be computed in $O(2^k n^{O(1)})$ time. Hence if the treewidth $k$ is small compared to the total size of the graph $n$, then this parameterized algorithm is much faster.
Output-sensitive analysis is a technique which is applied to construction problems, and also takes the size of the output into account in the run-time expression. A good example is the problem of determining the intersection points of a set of line segments in the plane. If I'm not mistaken you can compute the intersections in $O(n \log n + k)$ time where $k$ is the number of intersections.