Что такое оператор одеяла для сортировки вставки?

Question

Для каждого входа 'n' можно сказать, что верхняя граница сортировки вставки равна O (n^2), а нижняя граница - omega (n)? Или это только O (n^2) ?.

Answer 1

Для каждого ввода временная сложность O(n^2)+Omega(n)=O(n^2), потому что Omega(n) = O(n^2). Обратите внимание that

Обратите внимание, что «=» не предназначен для выражения «равно» в обычном математическом смысле, а скорее более разговорным «является»

Для второй части вашего вопроса, это зависит от того, какого типа нижней границы вы заинтересованы.

Omega (п), в лучшем случае, так что нижняя граница, по крайней мере Omega (п)

Если вы хотите нижняя граница для всех входов, то да. Рассмотрение лучшего ввода дает вам нижнюю границу. Если вам нужна нижняя граница для любых алгоритмов, решающих ту же проблему, вам необходимо рассмотреть алгоритм на все возможные входы.