Clarifying Big-Oh

Big-Oh notation was a weird concept to me at first, especially when Professor Heap told us that we could just choose to drop values from within the given functions. But after going through the steps it started to make a lot more sense.

Since we are saying that the function that we are making bigger is bounded above by a function that we are making smaller, even if we only have to multiply by a small constant factor. If it is true for that then it is true for all natural number.

Here's a run through from one of the tutorial examples:

Statement: ∃c ∈ R, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ 5n⁴ - 3n² + 1  ≤ c(6n⁵ – 4n³ + 2n)

      Pick c = 3, Then c ∈ R

       Pick B = 1, Then B ∈ ℕ

      Assume n ∈ ℕ                        # n is a generic natural number, to introduce ∀

                  Assume n ≥ B                        # assume antecedent, to introduce ⇒

                              Then 5n⁴ - 3n² + 1

• Since we're saying that  5n⁴ - 3n² + 1 is bound above by c(6n⁵ – 4n³ + 2n) we can continue to make it larger and if it is still bound above then we know it is true.

                              ≤ 5n⁴ + 1        # Remove (-3n)

• For all the natural numbers past the break point, we can safely prove that this will be bound above by this. 

                              ≤ 5n⁴ + n        # n ≥ 1 hence B = 1

                                             = 5n⁴  + n⁴

                                             = 6n⁵                      # Multiply by n

• Here we pick the c, so that this function is true for all natural numbers N. c this helps scale the function to make this true for all natural numbers.

                                             = 3(2n⁵)                     # c = 3

                              = c(6n⁵ – 4n⁵)

                              ≤ c(6n⁵ – 4n³)

                              ≤ c(6n⁵ – 4n³ + 2n)

• Since  c(6n⁵ – 4n³ + 2n) is what we are bounding by we can continue to make it smaller for the same reason stated above, because if this still bounds the bottom function above then it is true for the much larger function.

                              Then 5n⁴ - 3n² + 1  ≤ c(6n⁵ – 4n³ + 2n)

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

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

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

Test and Assignments !

Just got my test and assignment mark back and I'm extremely happy with how it turned out. As I stated in my previous post, the assignments do really help in preparing for the test. Of course reviewing the past test and reading all the lecture notes over also helped while also practicing everything we covered in tutorial and lectures to make sure I got down the concepts. It's strangely satisfying reaching the end of a proof and understanding why it makes sense.

Now we're moving on from that and going into Assignment 3, which I believe will cover much of what we have seen of Chapter 4. I think I'm ready for the challenge. I'm still a bit unsteady on some of the ideas of Chapter 4 like how we can just remove certain elements of a function. I understand why we do it, but it just seems strange. I think I'm to use to Calculus we're we can't just make things disappear.

Progress

It's weird but every time I learn something new in this class I find it extremely hard and feel doomed, but after practicing a bit here and there things seem to work out. The way this course is structured works out pretty well. In the sense that the Assignments help develop the skills i need to do well on the Tests. This and the steady pace keeps this, I find, at a manageable pace.

The slog has been a little slow lately and I'm sorry for that. Just keeping up with the assignment and preparing for the tests take up a lot of time.

StreetCar Drama is possible

When I had heard Professor Heap telling us about the street car problem, I didn't think it was possible but it seems it is. I was reading my friend Mandy's blog and she had figured it out. The solution can be found here: http://mandyxu.blog.com/2013/02/28/streetcar-drama/


Heres the problem:
A: Haven't seen you in a long time! How old are your three kids now?
B: The product of their ages (rounded down to the nearest year) is 36.
A: That doesn't really answer my question.
B: Well, the sum of their ages is (fire engine goes by)
A: That still doesn't tell me how old they are.
B: Well, the eldest plays piano.
A: Okay, I see: their ages are (you have to get off the streetcar)

The solution is actually pretty clever and the one tip that I can give without pretty much giving the answer a away is to write out the possible combinations of numbers. It always seems that carrying out a few sample solutions helps find patterns in this course. 

Proofs!

Working on the assignment after a busy week, I found the most challenging one to be question #6 to be one of the more challenging ones. It was hard to see how all the pieces fit together even when you have everything you need in front of you.

Though in the end it worked out, not it's more about organizing the structure and having appropriate comments which is kind of hard to determine. It's hard to decide what a good comment is for a proof and what is just starting the obvious.