Здравствуйте, garkus, Вы писали:

G>Верхняя асимптотическая граница есть подмножеством O(n*n) а нижняя Ω(n).
G>Получаться что O(n*n) не равно Ω(n).
G>Следует ли считать что для сортировки вставкой не существует
G>точной асимптотический границы?
Ага, для произвольных входных данных точной асимптотической оценки не существует.
Однако, если алгоритму на вход подавать лишь отсортированные (в нужном порядке) последовательности, можно сказать, что время его работы составляет Ө(n). Кстати, для алгоритма верны также границы Ω(1) и O(n^125)
Асимптотическая оценка — лишь обозначение количества требуемых ресурсов (времени или памяти) для некоторого множества входных данных.
На одном и том же множестве для худшего случая это будет O, для лучшего — Ω, если оценки совпадут, то появится еще и Ө.
В Кормене все доступно описано.