Асимптотические аналитические неравенства

Question

У меня проблема с пониманием того, как были получены следующие неравенства, выделенные красным цветом для этой проблемы асимптотического анализа. Может ли кто-нибудь объяснить природу этих неравенств и как они стали.

На следующем изображении находятся следующие проблемы: Часть, выделенная красным цветом, - это то, где я испытываю трудности с пониманием.

картину проблемы и решения

Answer 1

Препараты

Часть в изображении выше, выше красной маркировкой секции, является само определение для Big-thetas; нотации : "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 и 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 в (*) не уникальный: существует бесконечно много способов, чтобы показать, что (*) имеет место (если он делает), или она существует никто. Особый выбор автором вашего решения в этом случае естественным образом приходит, но мы могли бы выбрать любое количество других наборов констант.