证明函数f（n）属于大theta（g（n））

Question

它的练习要求指示该函数属于并证明主张的级别（g（n））。

在这种情况下，f（n）=（n^2+1）^10

根据定义，f（n）e big-theta（g（n））<=> c1*g（n）<f（n）<c2*g（n），其中c1和c2是两个常数。

我知道，对于这个特定的f（n），大theta是g（n^20），但我不知道谁能正确证明这一点。我想我需要操纵这种不平等，但我不知道如何

Answer 1

函数f（x）为θ（g（x）），iff：

• f（x）为o（g（x）），并且
• g（x）为o（f（x））

因此，虽然您可以尝试以单一的不平等来证明它，但建议您将其分解为这两个部分。首先证明了一些n> n₀ f（n）<c₁ g（n），然后证明一些n> n₀ g（n）<c₂ f（n）。一旦您分别证明了这两个部分，就可以回到θ的定义，以证明f =θ（g）。

Answer 2

我并不是真正的专家，但是您不能证明f（n）e o（n）和f（n）eΩ（n），然后争辩说f（n）eθ（n）由于交叉点的定义？