## Abstract

We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an unknown input distribution D. We assume here that D is of product type. More precisely, suppose that we need to process a sequence I_{1}, I_{2}, . . . of inputs I = (x_{1}, x_{2}, . . . , x_{n}) of some fixed length n, where each xi is drawn independently from some arbitrary, unknown distribution D_{i}. The goal is to design an algorithm for these inputs so that eventually the expected running time will be optimal for the input distribution D = π_{i} D_{i}. We give such self-improving algorithms for two problems: (i) sorting a sequence of numbers and (ii) computing the Delaunay triangulation of a planar point set. Both algorithms achieve optimal expected limiting complexity. The algorithms begin with a training phase during which they collect information about the input distribution, followed by a stationary regime in which the algorithms settle to their optimized incarnations.

Original language | English (US) |
---|---|

Pages (from-to) | 350-375 |

Number of pages | 26 |

Journal | SIAM Journal on Computing |

Volume | 40 |

Issue number | 2 |

DOIs | |

State | Published - 2011 |

## All Science Journal Classification (ASJC) codes

- General Computer Science
- General Mathematics

## Keywords

- Average case analysis
- Delaunay triangulation
- Low entropy
- Sorting