证明Big-Theta符号 [英] Proving Big-Theta notation

问题描述

你好，我已经尽力理解大θ，现在我得到了Big-Oh和Big-Omega的证明的主要概念，但是我找不到和我的职业相近的例子，因为我无法证明这一点：

Hello I've tried my best to understand big-theta and now I get the main conception of the proofs for Big-Oh and Big-Omega but i couldn't find and example that is close to my excercise, because i cant do the proof for that one:

通过展示证人来证明4n ^ 2 + 4n = Big-Theta（2n ^ 2 + 32n）

Prove, by exhibiting witnesses, that 4n^2 + 4n = Big-Theta(2n^2 + 32n)

我知道我必须为Big-Oh和Big-Omega进行证明，以便证明Big-Theta，但我不知道如何开始。我的意思是右边的方程式使我感到困惑。

I know that i have to prove it for Big-Oh and Big-Omega in order to prove Big-Theta, but i have no idea how to start. I mean the equation on the right side confuses me.

推荐答案

通过大θ的定义，您需要证明存在两个常数k1和k2，使得对于所有足够大的n值，

By the definition of big-theta, you need to show that there exist two constants, k1 and k2, such that for all sufficiently large values of n,

k1 * |2n^2 + 32n| <= |4n^2 + 4n| <= k2 * |2n^2 + 32n|

（由于函数对n均为正，因此可以删除绝对值。）每个不平等都可以分别得到满足，就可以了。

(Since your functions are all positive for positive n, you can drop the absolute values.) Just show that each inequality can be satisfied separately and you're done.

PS如果这是家庭作业，请标记它。

P.S. If this is homework, please tag it so.

这篇关于证明Big-Theta符号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！