Performance and Limitations of Metaheuristics

In contrast with exact algorithms whose worst-case time complexity is known (see Chapter 1), metaheuristics do not provide that kind of bound. They can be very effective on a given instance of a problem and, at the same time, show long running times on another without finding a satisfactory solution. On the other hand, for example, the selection sort algorithm could spend different amount of time on an already sorted list, and on a list sorted in the opposite order, but we know that, on any list permutation, its time complexity function T(n) will be bounded by a seconddegree polynomial and the list will be sorted correctly.

Authors and Affiliations

1. Département d’informatique, Université de Genève, Carouge, Switzerland

   Bastien Chopard

2. Faculté des hautes études commerciales (HEC), Université de Lausanne, Lausanne, Switzerland

   Marco Tomassini

Reprints and permissions

© 2018 Springer Nature Switzerland AG

Policies and ethics