Journal 7 - Week 8

Friday   October. 31st   Sunny

Hi everyone. Just a reminder that Assignment 2 is due next Monday. Also. term test 2 is in the next week. Don’t be worry about the busy coming week. Hopefully my journal could be a good review for everyone to prepare for test 2. 

Firstly, I will talk about something new to us in week 8. Formal definitions of O and Ω have been explained to us this week. Let me specify these two definitions here because they are very important. They follows as below.

A function f(n) is in O(n²) if and only if ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ f(n) ≤ c∙n²

A function f(n) is in Ω(n²) if and only if ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ f(n) ≥ c∙n²

We need to notice that the difference between O and Ω is that O is an upper bound and Ω is a lower bound. They are not easy to remember but we can do more exercise to get more familiar with them. Also, we can write them on our aid sheet during the tests and exam. 

I found a very interesting slog wrote by my classmates which talks about big-oh.
The link is as below:
http://165choi.blogspot.ca/2014/11/my-knowledge-is-getting-big-oh.html
If you still get stuck with the big-oh. Hopefully our slogs can help you.

On the other hand, we discussed worst-case analyses of two algorithms. This means we are starting to analysis more deeply with course contents, not just symbolization and proof, but how it works and why it works. 

Secondly, I will talk about the hardest part this week and how I am trying to make it easier for myself. Big-oh is about functions, which is harder than numbers and sequences which we learned before, since numbers will change by functions. This new concept challenged me, so I did a lot of exercises about big-oh of n² and feel much better for now.

Thirdly, I chose one of the proof questions in my exercise, which follows as below.

Q: Prove: ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

It is obvious that we need the definition of big-oh.

A graph could make the relationship between f(n) and g(n) more clear.

Proof:

Let c = 1. Then c∈R⁺.

Let B = 6. Then B∈N.

Assume n∈N.

       Assume n ≥ B.

              Then 5n⁴ - 3n² + 1 < 5n⁴ + 1

                                               ≤ 5n⁴ + n⁴ 

                                                = 6n⁴ 

                                               ≤ n⁵  ≤ 2n⁵ 

                                               ≤ 6n⁵ - 4n⁵ 

                                               ≤ 6n⁵ - 4n³ ≤ 6n⁵ - 4n³ + 2n

       Then n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

Then ∀n∈N, n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

Then ∃c∈R⁺, ∃B∈N, ∀n∈N, n ≥ B ⇒ 5n⁴ - 3n² + 1 ≤ c∙(6n⁵ - 4n³ + 2n)

Lastly, our tutorial of this week focused on proof by cases. One of the questions I have clearly explained in my last journal, which talked about proof by cases a lot. I think it is useful so I would not duplicate that topic.

This is the end of the journal.

Much appreciated for reading my journal.

See you next week :)