Чтобы показать, что каждый многочлен степени k равен O (n ^ k), мы должны показать, что существуют константы n0 и c такие, что для n> n0 a_k n ^ k + a_k-1 n ^ k- 1 +… + a_0 <= c * n ^ k. Если мы выберем c = | a_k | + | a_k-1 | +… + | A_0 |, тогда легко проверить, что RHS должна быть больше или равна LHS; иначе быть не может, поскольку каждый член в LHS соответствует члену в RHS, который должен быть больше или равен ему. </p>
Чтобы показать, что каждый многочлен степени k является Омега (n ^ k), мы должны показать, что существуют константы n0 и c такие, что для n> n0 a_k n ^ k + a_k-1 n ^ k-1 +… + a_0> = c * n ^ k. Чтобы продемонстрировать это, возьмите c = a_k / 2. Затем мы можем вычесть a_k / 2 n ^ k с обеих сторон, чтобы получить a_k / 2 n ^ k + a_k-1 n ^ k-1 +… + a_0> = 0 Этот многочлен имеет не более k действительных корней; пусть n0 будет наибольшим вещественным root многочлена. Тогда для всех n> n0 многочлен должен оставаться неотрицательным или неположительным. Предположим, это осталось неположительным. Тогда a_k / 2 n ^ k <= a_k-1 n ^ k-1 +… + a_0. Деление на n ^ k дает a_k / 2 <= a_k-1 / n +… a_0 / n ^ k. RHS этого неравенства является строго убывающей функцией, которая приближается к нулю при увеличении n без границы; следовательно, это неравенство не может быть верным вообще. Следовательно, многочлен остается неотрицательным после наибольшего root, n0; следовательно, исходный многочлен подтверждается как Омега (n ^ k) с c = a_k / 2 и n0, равным наибольшему root многочлена a_k / 2 n ^ k +… + a_0. </p>
Поскольку каждый многочлен степени является одновременно O (n ^ k) и Омега (n ^ k), поэтому он также является тэтой (n ^ k).