Asymptotic Analysis Inequalities

Question

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

Answer 1

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.