code_panik

Любая функция является своей точной асимптотической оценкой (как O-большое, так Ω-большое), поэтому в общем случае множество не пусто. Просто перечитайте аккуратно определение из книги на предыдущей странице. Там все константы положительные и все рассматриваемые функции асимптотически неотрицательные. Асимптотически положительная функция является асимптотически неотрицательной.

Пусть мы сортируем пузырьком последовательность из N элементов N, N - 1, N - 2, ..., 1 по возрастанию. Тогда число N сделает N - 1 шагов, пока не окажется на своем месте на последней позиции. Аналогично число N - 1 сделает N - 2 шага и т.д. Когда мы разместим на свои места все элементы 2, 3, ... N, единичка автоматически окажется на своем месте, другого ведь нет. Получим, что в худшем случае общее число шагов сортировки последовательности из N элементов - это сумма N - 1 слагаемых (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2 = | по формуле арифметической прогрессии | = (N - 1 + 1) * (N - 1) / 2.

Какие способы реализации взаимодействия двух тел реально используются в игровых движках?

Отскок - один из вариантов разрешения коллизий. Тема очень большая, ответы можно найти по запросам collision detection, collision resolution, collision response. Примеры материала:
https://blog.winter.dev/2020/designing-a-physics-e...
https://realtimecollisiondetection.net/books/rtcd/
Интересно, что каждое столкновение генерирует сигнал-событие, который должен быть обработан движком. Представьте, что у вас множество шариков падают на пол в ограниченном стенами пространстве. Шарики ударяются друг об друга, теряя энергию. Расстояния между ними становятся всё меньше, и в конечном итоге движок регистрирует такое количество событий, что всё виснет, и сам движок занимается только обработкой коллизий. Такое поведение нужно иметь в виду и обрабатывать соответствующим образом. То есть разрешение коллизий зависит от желаемых результата и точности симуляции. Например, в sokoban или тетрисе достаточно останавливаться в момент регистрации коллизии, в примере с шарами у нас continuous collision.
Примеры того, как сделано в реальных движках можно найти в выступлениях разработчиков на gdc, напр. https://www.gdcvault.com/play/1017644/Physics-for-...