Когда использовать большую нотацию O и когда использовать большую нотацию Theta

Question

Я понимаю, что Big O является верхней границей, а Big Theta - жесткой границей, когда, например, рассмотрим функции f (n) = O (g (n)) или аналогичным образом для Большой Теты. Но как мы узнаем, что конкретный алгоритм будет лучше представлен с использованием Big theta notation вместо Big O?

Например, временная сложность сортировки определяется как Большая Тета N^2, а не Большая О N^2, почему?

Answer 1

Речь идет не о том, что лучше, а о том, что вы хотите изучать. Если вы хотите изучить сценарий наихудшего случая, вы можете использовать верхнюю нотацию. Имейте в виду, что чем жестче граница, тем лучше, но в некоторых случаях трудно вычислить тугую границу. Вообще говоря, когда люди говорят о большой-O или большой тете, они имеют в виду то же самое, что и в выборе Сортировка, вы также можете использовать нотацию большого О.