Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
Instance optimality is a very interesting property of algorithms. One can generalize notions of instance optimality and come up with surprisingly interesting notions that include worst-case and average-case analysis.
Although it doesn't strictly fall under the purview of traditional algorithm analysis, it is interesting in its own right. The idea in a paper by Afshani-Barbay-Chan (FOCS '09) who discuss a geometric algorithm considers algorithm performance oblivious to input-order (which is relevant to their particular problem).
This might be seen to generalize as follows: For every algorithm partition the inputs into equivalence classes and consider the algorithm performance to be some sort of collective statistic over the average performance for each of these equivalence classes.
Worst-case analysis simply looks at the input as individual equivalence classes and computes the maximum running time. Average case analysis looks at the trivial equivalence class which is a single one comprising all inputs. In the Afshani-Barbay-Chan paper, their algorithm is optimal if the input is partitioned into classes of permutations (i.e., order oblivious performance).
It's not clear if this leads to any new paradigms of algorithm analysis. Tim Roughgarden's course has some excellent motivating examples and covers different methods to analyse algorithms.
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 < c < 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.
Adaptive Analysis measures the running time of polynomial time algorithms with respect to a multitude of parameters. For example, you want a sorting algorithm that runs in time $O(n \log n)$, but is much faster when the input is almost sorted. An adaptive analysis of a sorting algorithm would take into account the number of pairwise inversions, the number of runs, where a run is a maximal sorted consecutive part of the input, or the entropy of the input.
It looks like the Parameterized Analysis for polynomial-time algorithms, and it seems that the output-sensitive analysis fall in this category.
There's also "high probability" analysis (for randomized algorithms), where for any given instance you worry about how well your algorithm will perform most of the time, but can completely give up a small fraction of the time. This is common in learning theory.
You can add randomness to your algorithm, and combine it with all of the above. Then you will get, e.g., worst-case expected running time (worst-case instance, but averaged over all possible sequences of random coin flips in the algorithm) and worst-case running time with high probability (again, worst-case instance, but probability over the random coin flips in the algorithm).
Bijective analysis is a way to compare two algorithms (Spyros Angelopoulos, Pascal Schweitzer: Paging and list update under bijective analysis. J. ACM 60, 2013): Roughly, Algorithm A is better than Algorithm B on inputs of length n if there is a bijection f of the inputs of length n such that A performs on input x at least as good as B on f(x).
Competitive analysis
Used to compare online algorithms with the performance offline algorithms. See wikipedia page. The List Update problem is a classic example.
Competitive analysis In Page replacement algorithm, one method overweights the other by less page missing. Less page missing illustrates "less running time". Besides, competitive analysis is a method to compare two methods relatively. A good reference book is "ONLINE COMPUTATION AND COMPETITIVE ANALYSIS" from Allan Borodin.
