Hello and welcome to this week’s slog. This week will cover over week 9 and 10. Also, due to CDF being down this weekend, this week’s slog was a little delayed. In this slog I will talk about what has during these two weeks which mainly was about Big Oh and Big Omega. In my previous slog, I mentioned that I didn’t really understand Big Oh but after doing some examples in lectures, I sort of get how to do the proofs.

Basically from what I understand, when we want Big Oh, we are looking for the upper bound on the worst case running time for an algorithm for all inputs of any size. When we want to find if a function is in Big Oh of another function, in symbolic notation it would be:

f ∈ O(g)

What we are really saying, is:

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

What this means is that there exists a positive real number C, a natural number B, for every natural number n, such that if n is greater than or equal to B, then the function f, will be less than or equal to function g, multiplied by c. So since we are looking for the upper bound, we want to prove that the function f will be at most the function g or in other words, f is no worse than g in the worst case.

For Big Omega, it is slightly different where we are looking for the lower bound. When we want to find if a function is in Big Omega of another function, in symbolic notation it would be:

f ∈ Ω(g)

What we are really saying is:

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

Now the only difference between Big Oh and Big Omega is that the function f is at least as big as the function g or in other words, f is as bad as g in the worst case.

Okay, so let’s actually do an example.

Prove that 5n⁴ – 3n² + 1 ∈ O(6n⁵ – 4n³ + 2n)

So this statement in symbolic notation would be:

∃ C ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ 5n⁴ – 3n² + 1 ≤ c(6n⁵ – 4n³ + 2n)

So starting off, we need to pick a C and a B, but we don’t know what to pick yet, so we will have to do some work to figure it out. Also, how do we go about showing that the consequent is true? Let’s do some scratch work.

Let’s start by working on the left side

5n⁴ – 3n² + 1 ≤ 5n⁴ + 1 # The sum is definitely greater than or equal to the difference

                     ≤ 5n⁴ + n⁴  # n ≥ 1, basically rewrite 1 as n⁴

                     ≤ 6n⁴ # add the two terms together

                     ≤ n ^. n⁴ # Now if we set n ≥ 6, we can pick B to be 6

                     ≤ n⁵ # Add the exponents

Now, what? Well, I think that’s the most we can do for the left side, how about do some work the right side?

6n⁵ – 4n³ + 2n ≥ 6n⁵ – 4n³  #Just like for the left side, having a sum on one side will be                                                     # greater than or equal to just the difference of two terms

                       ≥ 6n⁵ – 4n⁵ # - n⁵ ≤ - n³

                       ≥ 2n⁵ # Subtract the two terms

                       ≥ n⁵ # Drop the 2, as we know that it will be greater than n⁵ by itself

Okay now we can piece these two together and start to write our proof

Pick C = __1__ then C ∈ ℝ⁺

Pick B = __6__ then B ∈ ℕ

Assume n ∈ ℕ and n ≥ B # Universal quantifier assumption and antecedent

            Then 5n⁴ – 3n² + 1 ≤ 5n⁴ + 1

                                           ≤ 5n⁴ + n⁴  # n ≥ 1

                                           ≤ 6n⁴

                                           ≤ n ^. n⁴ # n ≥ 6, so we can pick B to be 6

                                           ≤ n⁵

                                           ≤ 2n⁵

                                           ≤ 6n⁵ – 4n⁵

                                           ≤ 6n⁵ – 4n³ # - n⁵ ≤ - n³

                                           ≤ 6n⁵ – 4n³ + 2n # We can simply just chose C to be 1

Then ∀ n ∈ ℕ, n ≥ B ⇒ 5n⁴ – 3n² + 1 ≤ c(6n⁵ – 4n³ + 2n) #Introduce ∀ and ⇒

Then ∃ C ∈ ℝ+, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ 5n4 – 3n2 + 1 ≤ c(6n5 – 4n3 + 2n) #Introduce ∃

Then 5n⁴ – 3n² + 1 ∈ O(6n⁵ – 4n³ + 2n) #Conclude proof

The reason I chose this proof, which is a question from Tutorial #8, is because I was stuck at the part where we can’t do anything more to the left side of the consequent. I did not realize that we had to work backwards on the right side to get the two functions to match up. I decided to make this as an example to help explain Big Oh and also how to prove something in Big Oh.  

To show a proof where a function is not in Big Oh of another function, the symbolic notation would be:

f ∉ O(g)

Which says:

∀ C ∈ ℝ⁺, ∀ B ∈ ℕ, ∃ n ∈ ℕ, n ≥ B ∧ f(n) > c(g(n))

This time, we assume that under every positive real number C, and every natural number B, there exists a natural number n, such that n is greater than or equal to B and the function f is greater than the function g multiplied by c. This means that the function f is not bounded above by g and that the function f is worse than the function g.

For a function not in Big Omega of another function, the symbolic notation would be:

f ∉ Ω (g)

Which says:

∀ C ∈ ℝ⁺, ∀ B ∈ ℕ, ∃ n ∈ ℕ, n ≥ B ∧ f(n) < c(g(n))

So the function f is not bounded below by g and that the function f is better than the function g.

This is so far my understanding of Big Oh and Big Omega, as we get closer to the exam date, I hope to understand more of how do the proofs and the logic behind them as well. I hope by practicing through doing the questions on Assignment 3, I will be able to figure out how do them. Thanks for reading.