Быстрый выбор наихудшего сценария (Θ (n ^ 2) или O (n ^ 2)?)

Question

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

Например, Этот веб-сайт утверждает, что сложность времени в худшем случае составляет is (n ^ 2), а GeeksforGeeks утверждает, что это O (n ^ 2).

Может ли кто-нибудь помочь мне понять, какой из них правильный и почему это так?

Answer 1

Оба верны, но использование Θ является более сильным утверждением. Обозначение большого О дает асимптотику c верхней границы, тогда как обозначение большого тета дает фактическую асимптотику c скорость роста.

В качестве аналогии представьте, что Алиса и Боб подсчитывают чьи-то ноги. Алиса говорит legs = 2, а Боб говорит legs ≤ 2. Алиса и Боб оба правы, но утверждение Алисы сильнее.

При неформальном использовании довольно часто пишется O, когда вы могли бы написать более сильное утверждение с помощью just, просто потому, что у клавиш большинства людей нет Θ ключ.