Week in Review #6 (!): More with Big-O and completion of assignment and test #2

Has it really been two months since we started CSC165? Time whizzes by in the blink of an eye!

The next instalment in my "Week in Review" series is based on Big-O, which we looked at in weeks 8 and 9, as well as the recent assignment and test.

I had my second test on Wednesday. It was quick and straightforward, consisting of three proofs, just like the practice test. The last proof was on the definition of a floor function, or "the floor of x":

I thought, Wasn't this on the assignment? I could do this! The test was a lot easier than I thought and definitely easier than the first one. The testing effect does help a whole lot.

I've been more prepared for this test than the first test, and I think that this test was a success! Getting a low mark on the first test really motivated me to do better this time around! 

Part of my test preparation involved Assignment #2, due two days before the test. It took a while to finish, but I'm hoping I did well on that too. I managed to get some help from friends and a TA at the CS Help Centre. 

This week, we began proving the Big-O of polynomials. We've been practicing a lot of proofs, and so proving them wasn't too difficult. We started by writing a proof structure followed by writing up the actual proof.

Last week was introduction to Big-O. We started off by proving the Big-O of n², which is extremely long and mentally exhausting. I was quite relieved when we were introduced to proving the Big-O of polynomials because they aren't as long and complicated.

The definition of Big-O is as follows:

(for any function, f, that inputs natural numbers and releases non-negative real numbers)

The statement that needs to be proven is:

We start off by picking a positive real number, c, and a natural number, b, that will work. Then we assume that n is a generic natural number in order to introduce ∀. We assume the antecedent, n ≥ B. I'll put it all together using a proof structure:

Let c' = ____ and B' = _______.

Then c' ∈ R⁺and B' ∈ N.

Assume n ∈ N. # in order to introduce ∀

       Assume n ≥ B'. # antecedent; B is an arbitrary natural number

            .

            .

            .

Then ∀ n ∈ N, n ≥ B ⇒ g(n) ≤ cf(n) # introduce ∀ and ⇒

Then ∃ c ∈ R⁺, ∃ B ∈ N, ∀ n ∈ N, n ≥ B ⇒ g(n) ≤ cf(n) # introduce ∃ for b and c

Big-O of n², worst case, and the upper and lower bounds are still a bit unclear to me, so I'll go to office hours when I can, read the course notes, and practice a lot. I get the proof structure, but the actual proof is complicated and doesn't come to me just as easily.