渐近分析不等式(Asymptotic Analysis Inequalities)

我有一个问题，理解如何为这个渐近分析问题推导出以下红色突出显示的不等式。 有人可以解释这些不平等的性质以及它们是如何形成的。

以下图片有问题和解决方案。 用红色突出显示的部分是我无法理解的地方。

图片问题和解决方案

I have a problem understanding how the following inequalities highlighted in red were derived for this asymptotic analysis problem. Could someone explain the nature of these inequalities and how they came to be.

The following picture has the problem and solution. The part highlighted in red is where I am having trouble understanding.

Picture of the problem and solution

最满意答案

准备工作

上面图像中红色标记部分上方的部分是Big-Θ符号的定义：“ f(n) Θ(g(n)) ”，

f(n) = (n + a)^b, b > 0 (+) g(n) = n^b (++)

我们将重复这个不等式，以便在显示它如下所示时简化参考：

f(n) is in Θ(g(n)) with f(n) and g(n) as in (+) and (++), respectively <=> c_1⋅n^b ≤ (n + a)^b ≤ c_2⋅n^b, for some positive constants c_1, c2 (*) for n ≥ n_0, with n_0 constant > 0

因此，我们想要找到一些c_1 ， c_2和n_0 ，使(*)成立。

---

解决方案（彻底解释）

现在，因为b > 0 ，我们可以证明如果以下两个不等式成立，则(*)成立：

n + a ≥ k_1⋅n, for n > n_0 (i) n + a ≤ k_2⋅n, for n > n_0 (ii)

对于一些正常数k_1和k_2 （其与c_1和k_2^b = c_2 ，分别为k_1^b = c_1和k_2^b = c_2 ）。

表明(ii)持有

我们首先要表明(ii)对某些正常数k_1持有。 为此， 我们可以自由选择 n_0 ，使得n_0 ≥ |a| （因为a只是一个常数）。

=> n ≥ |a| ≥ a, since n ≥ n_0 ≥ |a| Hence: n + a ≤ n + |a| ≤ n + n = 2⋅n, for n ≥ n_0 ≥ |a| (II)

现在，用(II)我们已经表明(ii)成立，其中k_1 = 2且n_0是任何大于abs(a) ， n_0 ≥ |a| 。

显示(i)持有

现在展示(i) ：我们首先注意到以下不等式总是成立：

n + a ≥ n - |a| (†)

（如果a为负数，则实际上是相等的）。 现在，从上面回想一下， (II)适用于任何n_0 ≥ |a| 。 好吧，让我们选择将我们的n0固定在2⋅|a| （再次注意：我们可以自由选择我们想要表明不等式(*)成立的常数。

Choose n_0 as n_0 = 2⋅|a| (††)

因此，从(†) ：

n + a ≥ n - |a| ≥ n - n/2 = n/2 (†††) ^ | Why? Since from (††): |a| = n_0/2 < n/2, since n>n_0 We repeat (†††) without the middle stuff: n + a ≥ (1/2)⋅n, for n > n_0 = 2⋅|a| (I)

并且(I)现在简单地(i)对于k_2 = 1/2并且n_0 = 2⋅|a| 。

---

包起来

我们总结一下：

(I) & (II) => (1/2)⋅n ≤ n + a ≤ 2⋅n With b>0, this yields: ((1/2)⋅n)^b ≤ (n + a)^b ≤ (2⋅n)^b (**)

使用(**) ，我们已经证明(*)成立

c_1 = k_1^b = (1/2)^b = 2^(-b) c_2 = k_2^b = 2^b (note that the solution you posted has an error here) n_0 = 2⋅|a|

因此，我们已经证明， (+)中的f(n)在Θ(g(n)) ， g(n)在(++) 。

---

最后请注意， (*)中常量c_1 ， c_2 （ k_1 ， k_2 ）和n_0的选择不是唯一的：存在无限多种方式来表示(*)成立（如果存在），或者它不存在。 在这种情况下，您的解决方案的作者的特定选择自然而然，但我们可以选择任意数量的其他常量。

Preparations

The part in the image above, above the red-marked section, is the very definition for the Big-Θ notation: "f(n) in Θ(g(n))", with

f(n) = (n + a)^b, b > 0 (+) g(n) = n^b (++)

We'll repeat this inequality to simplify reference when showing that it holds below:

f(n) is in Θ(g(n)) with f(n) and g(n) as in (+) and (++), respectively <=> c_1⋅n^b ≤ (n + a)^b ≤ c_2⋅n^b, for some positive constants c_1, c2 (*) for n ≥ n_0, with n_0 constant > 0

Hence, we want to find some c_1, c_2 and n_0 such that (*) holds.

---

Solution (thoroughly explained)

Now, since b > 0, we can prove that (*) holds if the follow two inequalities hold:

n + a ≥ k_1⋅n, for n > n_0 (i) n + a ≤ k_2⋅n, for n > n_0 (ii)

for some positive constants k_1 and k_2 (which relates to c_1 and c_2 as k_1^b = c_1 and k_2^b = c_2, respectively).

Showing that (ii) holds

We'll begin with showing that (ii) holds for some positive constant k_1. To do this, we can freely choose n_0 such that n_0 ≥ |a| (since a is just a constant).

=> n ≥ |a| ≥ a, since n ≥ n_0 ≥ |a| Hence: n + a ≤ n + |a| ≤ n + n = 2⋅n, for n ≥ n_0 ≥ |a| (II)

Now, with (II) we have showed that (ii) holds, with k_1 = 2 and n_0 being any value larger than abs(a), n_0 ≥ |a|.

Showing that (i) holds

Now for showing (i): we start by noting that the following inequality always holds:

n + a ≥ n - |a| (†)

(and is in fact equality if a is negative). Now, recall from above that (II) holds for any n_0 ≥ |a|. Alright, lets choose to fix our n0 at 2⋅|a| (note again: we can freely choose the constants we want to show that inequalities (*) holds).

Choose n_0 as n_0 = 2⋅|a| (††)

Hence, from (†):

n + a ≥ n - |a| ≥ n - n/2 = n/2 (†††) ^ | Why? Since from (††): |a| = n_0/2 < n/2, since n>n_0 We repeat (†††) without the middle stuff: n + a ≥ (1/2)⋅n, for n > n_0 = 2⋅|a| (I)

And (I) now is simply (i) for k_2 = 1/2 and n_0 = 2⋅|a|.

---

Wrapping up

We summarize:

(I) & (II) => (1/2)⋅n ≤ n + a ≤ 2⋅n With b>0, this yields: ((1/2)⋅n)^b ≤ (n + a)^b ≤ (2⋅n)^b (**)

With (**), we have showed that (*) holds, with

c_1 = k_1^b = (1/2)^b = 2^(-b) c_2 = k_2^b = 2^b (note that the solution you posted has an error here) n_0 = 2⋅|a|

Hence, we have showed that f(n) as in (+) is in Θ(g(n)), with g(n) as in (++).

---

Finally note that the choices of constants c_1, c_2 (k_1, k_2) and n_0 in (*) is not-unique: there exist infinitely many ways to show that (*) holds (if it does), or it exists none. The particular choices by the author of your solution just comes naturally in this case, but we could've chosen any number of other set of constants.