algorithm - 你如何证明一个序列的大θ是它的首项？

Question

如果 f(x) = (An) x^n + (An-1) x^(n-1) +...+ (A1)x + (A0)你如何证明 f(x) 是大 theta(x^n)。

我已经考虑过了，可以通过证明 f(x) 大 O(x^n) 和 x^n 大 O(f(x)) 来实现。我已经找到了前者的证明(使用三角不等式)，但无法理解如何证明后者。

或者可以证明 f(x) 是大 omega (x^n)。

我一直卡在这个问题上，你能给我的任何提示或线索都会有很大帮助。

Answer 1

考虑 |An x^n + A(n-1) x^(n-1) + ... |/|x^n|作为 x -> oo。

表达式非常接近|An|如果 An 不为零，则对于足够大的 x，表达式将至少为 |An|/2。