漸近分析不等式

Question

對於這個漸近分析問題，我有一個理解如何導出以紅色突出顯示的不等式的問題。有人能解釋這些不平等的性質以及它們是如何形成的。

下面的圖片有問題和解決方案。以紅色突出顯示的部分是我無法理解的地方。

圖片的問題和解決方案的

Answer 1

製劑

圖像中的部分的上方，紅標記的區域的上方，是爲大-Θ表示法非常定義：「f(n) in Θ(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和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的選擇不是唯一的：存在着無限多的方式來表明(*)持有（如果這樣做），或者存在沒有。在這種情況下，解決方案作者的特定選擇就會自然而然地發生，但我們可以選擇任意數量的其他常量。