Big O-Me-Ga' Let's Go From Left to Right

Big Omega is related to Big Oh in the way that, while the latter defines an upper bound, the former defines a lower bound for a given function. This is done, usually, by expressing the function in a simpler function, akin to the Big Oh's expression. In mathematical form, it takes the following shape:

f(x) ∈ Ω(g(x))

The full definition would be the following:

∃ c ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ f(x) ≥ c(g(x))

This is identical to the definition of Big Oh, except that instead of f(x) ≤ c(g(x)) we have f(x) ≥ c(g(x)). This shows how this second equation approaches the function from the other side, thus defining a lower bound. Once again, we need to use proofs to establish whether the left side of the inequality is equal to the right side of the inequality. To go from left to right, we need to be, once again, creative.

Let's work with the following example:

8n^4 + 5n^2 - n ∈ Ω(-n^5 + 2n^3 - 4)

Then this would be equal to:

∃ c ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ 8n^4 + 5n^2 - n ≥ c(-n^5 + 2n^3 - 4)

First, we should work on the inequality

8n^4 + 5n^2 - n ≥ 8n^4 + 5n^2 #we remove -n to start off the inequality

                          ≥ 8n^2 + 5n^2 #since n^4 ≥ n^2, this inequality would still be true

                          ≥ 13n^2 #addition

                          ≥ n∙n^2 #since we have 13 as a coefficient, we could make B = 13 so that n ≥ 13

                          ≥ n^3 #multiplication

                          ≥ 2n^3 - n^3 #still n^3

                          ≥ 2n^3 - n^5 #since - n^5 ≤ - n^3 this is still true

                          ≥ -n^5 + 2n^3 - 4 #subtracting 4, this is still true

                          ≥ 1(-n^5 + 2n^3 - 4) #we could make c = 1

We have established values for both c and B, so that c = 1 and B = 13. In order to work the proof, we would have to do the following arrangement:

8n^4 + 5n^2 - n ∈ Ω(-n^5 + 2n^3 - 4)

∃ c ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ 8n^4 + 5n^2 - n ≥ c(-n^5 + 2n^3 - 4)

Assume n ∈ ℕ and n ≥ 13 #domain assumption and antecedent

    Then 8n^4 + 5n^2 - n ≥ 8n^4 + 5n^2 #add n

                          ≥ 8n^2 + 5n^2 #since n^4 ≥ n^2

                          ≥ 13n^2 #add both together

                          ≥ n∙n^2 #since n ≥ 13

                          ≥ n^3 #multiply both together

                          ≥ 2n^3 - n^3

                          ≥ 2n^3 - n^5 #since - n^5 ≤ - n^3

                          ≥ -n^5 + 2n^3 - 4 #subtract 4

    Then ∀ n ∈ ℕ, n ≥ B ⇒ 8n^4 + 5n^2 - n ≥ c(-n^5 + 2n^3 - 4) #introduce ⇒

Then 8n^4 + 5n^2 - n ∈ Ω(-n^5 + 2n^3 - 4) #introduce Big Omega

Done!