Измените изображения с прокси HTTP

По сути, вы можете использовать Big-only только в том случае, если между верхней и нижней границами времени выполнения алгоритма нет асимптотического разрыва:

В вашем примере сортировка вставкой занимает максимум O (n ^ 2) время (в худшем случае) и занимает Ω (n) время (в лучшем случае). Итак, O (n ^ 2) - верхняя граница времени алгоритма, а Ω (n) - нижняя граница алгоритма. Поскольку эти два не совпадают, вы не можете использовать Big-Θ для описания времени выполнения алгоритма сортировки вставок.

Однако рассмотрим алгоритм Selection-Sort . Время его наихудшего времени работы равно O (n ^ 2), а время наработки в лучшем случае - Ω (n ^ 2). Следовательно, поскольку верхняя граница и нижняя граница совпадают (асимптотически), можно сказать, что время выполнения алгоритма сортировки выбора равно Θ (n ^ 2).