}}
Пусть Предположим, что значение функции приспособленности в данный момент <tex>k</tex>. Тогда путей не менее <tex>k/2</tex>. Если путь является циклом, то в нем есть хотя бы одна вершина, соединяющая данный путь с каким-то другим, то есть найдется пара <tex>(u, w)</tex>, к которой можно применить мутацию и уменьшить количество путей. Если путь не является циклом, то так же найдется пара, при применении к которой мутации либо уменьшится количество путей, либо путь замкнется в цикл. Количество мутаций, которые уменьшают функцию приспособленности <tex>\Omega(k)</tex>. Как следствие, вероятность выбрать подходящую пару <tex>\Omega(q \cdot k)</tex>, где <tex>q</tex> — вероятность выбрать подходящую пару. Поэтому ожидаемое время достижения улучшения будет <tex>O(1/k \cdot q)</tex>. Изначально значение функции приспособленности не более <tex>2m</tex>. Суммируя по всем <tex>k</tex> без учета констант получаем:
