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

Алгоритмическая сложность обычно записывается в нотации Большого O (Big O), которая описывает асимптотическую оценку времени выполнения или использования памяти алгоритмом в зависимости от размера входных данных.

• Пузырьковая сортировка имеет сложность O(n²) в худшем и среднем случаях, так как каждый элемент сравнивается с каждым другим.

• Быстрая сортировка в среднем работает за O(n log n), но в худшем случае (например, когда массив уже отсортирован и выбирается плохой опорный элемент) может деградировать до O(n²).

Пример записи:

Пузырьковая сортировка: O(n^2)
Быстрая сортировка: O(n log n) в среднем, O(n^2) в худшем случае