[问题如下：证明每个度为k的多项式p（n）= a_k n ^ k + a_k-1 n ^ k-1 + ... + a_0（a_k> 0）属于theta（n ^ k）。
我不确定从哪里开始。
为了证明度数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中的一个术语相对应，该术语必须大于或等于它。
为了证明每个k阶多项式都是Omega（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为多项式的最大实根。然后，对于所有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的增加而无穷大，趋近于零；因此，这种不平等一般不能成立。因此，多项式在最大根n0之后保持非负值。因此，原始多项式被确认为Omega（n ^ k），其中c = a_k / 2且n0等于多项式a_k / 2 n ^ k +…+ a_0的最大根。
因为每个次数的多项式同时为O（n ^ k）和Omega（n ^ k），因此它也是Theta（n ^ k）。