CSC 165: big-Omega, big-Theta, general properties

Week #10

Topic: big-Omega, big-Theta, general properties

I had mentioned before that this course has some similarities with MAT137. When analyzing this week’s material I realized that the connection between these two courses is really strong. For instance, the new bound that combines both big-Omega and big-Theta looks very similar to the mathematical concept of Pinching theorem. Also, the way in which we proved the general statements about two functions is quite similar to proving limit laws. In the following part I will try to show how related CSC165 AND MAT137 are.

CSC 165

·         f ∈ O1 (g)

{f: ℕ ↦ ℝ^≥0 | ∃ c₁ ∈ ℝ⁺, ∃ c₂ ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ c₁ g(n) ≤ f (n) ≤ c₂ g(n)}

Application

Let’s apply this concept to – (n²) < 0 < n² in which case n is any typical natural number, c₁ = 1, c₂ = -1, and B ≥ 0

 

MAT 137

·         Pinching Theorem

Let f, g, h be functions

If ∃ p > 0 such that 0 < |n –a | < p and

 g(n) ≤ f (n) ≤ h(n) and the limit of both g(n) and h(n) are the same as n approaches a.

Then, the limit of f(n) as n approaches a is the same as the ones above

Application

x < x sin(1/x) < -x

 

Connection: If we look at the graph that deals with the pinching theorem we notice that ∀ x ∈ ℕ when B ≥ 0, x sin(1/x) is between x and –x or what is the same, between c₁x and c₂x, in which case c₁ is 1 and c₂ is -1. Exactly as happens with the new bound learned this week.

PROOFS

CSC165                                             

Prove F = {f: ℕ ↦ ℝ^≥0} ∀ f, g, h ∈ F,

(f ∈ O(h) ∧ g ∈ O(h)) ⇒ f + g ∈ O(h)

Assume f, g, h ∈ F # Introduce ∀

Assume (f ∈ O(h) ∧ g ∈ O(h)) #Antecedent

Then ∃ c_f ∈ ℝ⁺, ∃ B_f ∈ ℕ, ∀ n ∈ ℕ, n ≥ B_f ⇒ f(n) ≤ c_f * (h(n))

Then ∃ c_g ∈ ℝ⁺, ∃ B_g ∈ ℕ, ∀ n ∈ ℕ, n ≥ B_g ⇒ g(n) ≤ c_g * (h(n))

Prove ∃ c ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ f(n) + g(n) ≤ c * (h(n))

Pick c = c_f + c_g. Then c ∈ ℝ⁺

Pick B = max (B_f, B_g). Then B ∈ ℕ

Assume n ∈ ℕ, n ≥ B

Then (f + g) (n) = f(n) + g(n) ≤ c_f * (h(n)) + c_g * (h(n)) 
#By assumption n≥ B, n ≥ B_f and n ≥ B_g

                                                            ≤ (c_f + c_g) * (h(n))

                                                            = c * (h(n)) # c =  c_f + c_g

Conclude ∀ f, g, h ∈ F, (f ∈ O(h) ∧ g ∈ O(h)) ⇒ f + g ∈ O(h)

MAT 137

Prove If the limit of f(x) as x approaches a is equals L and the limit of g(x) as x approaches a is equals M. Then the limit of f(x) + g(x) as x approaches a is equal to L + M

Asume  = L and the limit of f(x) as x approaches a is equals L and the limit of g(x) as x approaches a is equals M.

Then ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(f(x)) - L| < e₁ = e/2

Then ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(g (x)) - M| < e₂ = e/2

Prove ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(f(x) + g(x)) – (L + M)| < e

Assume e ∈ ℝ

Take d= min(d1, d2)

Assume x ∈ ℝ ∧ |x – a | < d

Then  |(f(x) + g(x)) – (L + M)| = |(f(x) - L) + (g(x) - M)| ≤ |(f(x) - L)| + |(g(x) - M)|

= e/2 + e/2 = e

Conclude ∀ e ∈ ℝ, ∃ d ∈ ℝ, ∀ x ∈ ℝ, |x – a | < d ⇒ |(f(x) + g(x)) – (L + M)| < e

Connection

In both cases, we assumed two things and used our assumptions to prove the final result. Even though these two proofs prove something completely different, they follow the same principle and use the same tools