Запутанный, чтобы выразить сложность времени с тэта-нотацией или Big Oh-нотацией

Question

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

Должны ли мы выбрать выражение сложности времени в виде O(n) или theta(n)?Поскольку функция f(n) может быть выражена как Big-Oh(g(n)) или theta (g(n)).

Когда мы выбираем big-oh вместо theta?

Answer 1

Используйте обозначение Big Theta, если вы также хотите указать нижнюю границу. f(n) = O(g(n)) говорит, что f ограничен сверху g, тогда как f(n) = Theta(g(n)) говорит, что f ограничен как сверху, так и снизу g.

Другими словами, существуют константы k1 и k2, такие что k1 * |g(n)| <= |f(n)| <= k2 * |g(n)|