3-1 Asymptotic behavior of polynomials

Let

\[p(n) = \sum_{i = 0}^d a_i n^i,\]

where \(a_d > 0\), be a degree-\(d\) polynomial in \(n\), and let \(k\) be a constant. Use the definitions of the asymptotic notations to prove the following properties.

a. If \(k \ge d\), then \(p(n) = O(n^k)\).

b. If \(k \le d\), then \(p(n) = \Omega(n^k)\).

c. If \(k = d\), then \(p(n) = \Theta(n^k)\).

d. If \(k > d\), then \(p(n) = o(n^k)\).

e. If \(k < d\), then \(p(n) = \omega(n^k)\).

Let's see that \(p(n) = O(n^d)\). We need do pick \(c = a_d + b\), such that

\[\sum\limits_{i = 0}^d a_i n^i = a_d n^d + a_{d - 1}n^{d - 1} + \cdots + a_1n + a_0 \le cn^d.\]

When we divide by \(n^d\), we get

\[c = a_d + b \ge a_d + \frac{a_{d - 1}}n + \frac{a_{d - 2}}{n^2} + \cdots + \frac{a_0}{n^d}.\]

and

\[b \ge \frac{a_{d - 1}}n + \frac{a_{d - 2}}{n^2} + \cdots + \frac{a_0}{n^d}.\]

If we choose \(b = 1\), then we can choose \(n_0\),

\[n_0 = \max(da_{d - 1}, d\sqrt{a_{d - 2}}, \ldots, d\sqrt[d]{a_0}).\]

Now we have \(n_0\) and \(c\), such that

\[p(n) \le cn^d \quad \text{for } n \ge n_0,\]

which is the definition of \(O(n^d)\).

By chosing \(b = -1\) we can prove the \(\Omega(n^d)\) inequality and thus the \(\Theta(n^d)\) inequality.

It is very similar to prove the other inequalities.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用