CSC 165 big-Oh of polynomials, non-polynomials, limits

Week #9

Topic: big-Oh of polynomials, non-polynomials, limits

This week we talked about the big-Oh of polynomials. Polynomials seem to be a more accessible expression to work with. However, there is still a few observations that have to be made in order to master this topic.

One thing to remember when tackling this kind of problem is that we always follow a similar structure. In general terms, the structure is as follows:

O (n²) = {f: ℕ ↦ ℝ^≥0 | ∃ c ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ f (n) ≤ cn²}

This is very similar to the structure to prove upper and lower bounds. For this reason, working with polynomials made me clarify my thoughts about the big-Oh proofs that dealt with counting steps and finding the worst-case.

Now, I understand that the argument in O (n²) determines the expression on the left hand side (f (n) ≤ cn²), which also happens for the worst case of n in (Ws (n) ≤ cn²).

Working with polynomials also made me understand how to pick a proper B. A case that we have to be careful with is when we have a constant:

k ≤ n²  only if n > 0, because otherwise, if n=0 then k is no longer less than n².

In order to practice this week´s material I decided to work on the following exercise:

Prove 4 n² + 5n + 6 ∈ O (n² + 5n)

O (n²) = {f: ℕ ↦ ℝ^≥0 | ∃ c ∈ ℝ⁺, ∃ B∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ 4 n² + 5n + 6  ≤ c (n² + 5n)}

Pick c = 15. Then c ∈ ℝ⁺

Pick B = 1. Then B ∈ ℕ

Assume n ∈ ℕ #any typical natural number

            Assume n ≥ B # Antecedent

                        Then 4 n² + 5n + 6 ≤ 4 n² + 5 n² + 6 ≤ 4 n² + 5 n² + 6 n²

                                                                                   = 15 n² = c n² ≤ c (n² + 5n) 
                                                                                   # c = 15 ∧ B ≥ 1  

            Then n ≥ B ⇒ 4 n² + 5n + 6 ≤ c (n² + 5n) # Introduce implication

Then ∀ n ∈ ℕ, n ≥ B ⇒ 4 n² + 5n + 6 ≤ c (n² + 5n) # Introduce universal

Then ∃ B∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ 4 n² + 5n + 6 ≤ c (n² + 5n) # Introduce existential

Then ∃ c ∈ ℝ⁺, ∃ B∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ 4 n² + 5n + 6 ≤ c (n² + 5n) # Introduce existential

Then 4 n² + 5n + 6 ∈ O (n² + 5n) matches the definition.