<p>I have two more for the list, which are somewhat similar.</p>

<ol>
<li><p>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.</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 2.5
2010-09-03T09:52:09.837Z
2010-09-03T09:52:09.837Z
Bart Jansen
<p><strong><a href="http://www.glencora.org/silent-glen-speaks/adaptive-analysis/">Adaptive Analysis</a></strong> 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 <a href="http://en.wikipedia.org/wiki/Inversion_%28computer_science%29">inversions</a>, the number of runs, where a run is a maximal sorted consecutive part of the input, or the <a href="http://en.wikipedia.org/wiki/Entropy_%28information_theory%29">entropy</a> of the input.</p>

<p>It looks like the Parameterized Analysis for polynomial-time algorithms, and it seems that the output-sensitive analysis fall in this category.</p>

CC BY-SA 2.5
2010-09-05T05:03:31.267Z
Serge, thanks for the link to Glencora's blog post, lots of interesting comments there.
umar
CC BY-SA 2.5
2010-09-03T14:52:24.140Z
2010-09-03T14:57:47.257Z
2010-09-03T14:57:47.257Z
Serge Gaspers
<p>There's also "<b>high probability</b>" 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. </p>

CC BY-SA 2.5
2010-09-03T06:09:53.620Z
2010-09-03T15:05:05.003Z
2010-09-03T15:05:05.003Z
Lev Reyzin
<p>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).</p>

CC BY-SA 2.5
2010-09-03T08:45:54.737Z
2010-09-03T08:45:54.737Z
Jukka Suomela
<p><em>Bijective analysis</em> 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).</p>

CC BY-SA 3.0
2013-10-15T19:08:56.790Z
2013-10-15T19:08:56.790Z
Bodo Manthey
<p><strong>Competitive analysis</strong></p>

<p>Used to compare online algorithms with the performance offline algorithms. See <a href="http://en.wikipedia.org/wiki/Competitive_analysis_%28online_algorithm%29" rel="nofollow">wikipedia page</a>. The List Update problem is a classic example.</p>

CC BY-SA 2.5
2010-09-03T11:05:52.520Z
But it is not used to analyse *"the running time of an algorithm"*.
Jukka Suomela
CC BY-SA 2.5
2010-09-03T11:03:29.457Z
2010-09-03T11:03:29.457Z
Rui Ferreira
<p>Competitive analysis
In <a href="http://en.wikipedia.org/wiki/Page_replacement_algorithm" rel="nofollow">Page replacement algorithm</a>, 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.</p>

CC BY-SA 2.5
2010-09-06T01:26:59.130Z
2010-09-06T01:26:59.130Z
Jing
<p>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. </p>

<p>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). </p>

<p>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.</p>

<p>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). </p>

<p>It's not clear if this leads to any new paradigms of algorithm analysis.
<a href="http://theory.stanford.edu/~tim/f09/f09.html">Tim Roughgarden's course</a> has some excellent motivating examples and covers different methods to analyse algorithms. </p>

CC BY-SA 2.5
2010-09-05T05:04:23.090Z
Ananth, thanks a lot for the link to Tim's course. That's exactly the sort of thing I was looking for.
umar
CC BY-SA 2.5
2010-09-05T04:10:46.523Z
2010-09-05T04:43:41.997Z
2010-09-05T04:43:41.997Z
Ananth
<p>Here are some ways to analyze the running time of an algorithm:</p>

<p>1) Worst-case analysis: Running time on the worst instance.</p>

<p>2) Average-case analysis: Expected running time on a random instance.</p>

<p>3) Amortized analysis: Average running time on the worst sequence of instances.</p>

<p>4) Smoothed analysis: Expected running time on the worst randomly perturbed instance.</p>

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

<p>My question: Is this a complete list?</p>

CC BY-SA 2.5
2010-09-06T21:31:21.817Z
I guess that this kind of list can never be exhaustive.
Tsuyoshi Ito
<ds.algorithms>
Other kinds of running time analysis besides worst-case, average-case, etc?
umar
# Other kinds of running time analysis besides worst-case, average-case, etc?

(Asked by: username_0 on 2010-09-03)

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?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: I guess that this kind of list can never be exhaustive.  

---

## 8 answers

### Answer by username_9 on 2010-09-05. Score: 8 | Accepted answer

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](http://theory.stanford.edu/~tim/f09/f09.html) has some excellent motivating examples and covers different methods to analyse algorithms.

> **Comments:**
> **username_0**: Ananth, thanks a lot for the link to Tim's course. That's exactly the sort of thing I was looking for.  

---

### Answer by username_2 on 2010-09-03. Score: 14

I have two more for the list, which are somewhat similar.

1. 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.
2. 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.


---

### Answer by username_3 on 2010-09-03. Score: 8

**[Adaptive Analysis](http://www.glencora.org/silent-glen-speaks/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](http://en.wikipedia.org/wiki/Inversion_%28computer_science%29), the number of runs, where a run is a maximal sorted consecutive part of the input, or the [entropy](http://en.wikipedia.org/wiki/Entropy_%28information_theory%29) 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.

> **Comments:**
> **username_0**: Serge, thanks for the link to Glencora's blog post, lots of interesting comments there.  

---

### Answer by username_4 on 2010-09-03. Score: 7

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.


---

### Answer by username_5 on 2010-09-03. Score: 4

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).


---

### Answer by username_6 on 2013-10-15. Score: 3

*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).


---

### Answer by username_7 on 2010-09-03. Score: 1

**Competitive analysis**

Used to compare online algorithms with the performance offline algorithms. See [wikipedia page](http://en.wikipedia.org/wiki/Competitive_analysis_%28online_algorithm%29). The List Update problem is a classic example.

> **Comments:**
> **username_5**: But it is not used to analyse *"the running time of an algorithm"*.  

---

### Answer by username_8 on 2010-09-06. Score: 0

Competitive analysis
In [Page replacement algorithm](http://en.wikipedia.org/wiki/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.


---

