Week 8- Formal definition of big-Oh and its proof structure

        In this week's class, I was taught the formal definition of O(f(n)), which is referred to as the asymptotic upper-bound:

By categorizing a function as O(f(n)) means that the function grows no faster f(n). And this definition simply means beyond breakpoint B, the function g is upper-bounded by f(n).

        An example is to prove that the function f(n)=2n^2 + 1 is upper-bounded by n^2:

The detailed proof structure for this is:

Because the definition for upper-bound begins with there exists, my first line for the proof begins with choosing a c' and a B'. However since I do not know how the proof will turn out, I left the values for c' and B' blank for now. I then proceed to the next line by stating that the values I chose for c' and B' matches their given domain. I then assume a generic natural number n because of its universal quantifier. On the same line, I also assumed the antecedent to be true. Then I squared the antecedent. Since I want to arrive at the equation that 2n^2 + 1 is less than or equal to cn^2, I made B' equal to 1 for simplicity. Hence n^2 is greater than or equal to 1. Because I chose a value for B', I go back and fill in the first line with B' = 1. And since 1 is a natural number, my choice is applicable.  Then, I added 2n^2 to both sides of the inequality, and simplified it to 2n^2 + 1 is less than or equal to 3n^2. Now, it is obvious that in order to prove  2n^2 + 1 is less than or equal to cn^2, all I need is to make c' equal to 3.

        In conclusion, during tests, it is much easier to figure out a value for B' and c' on a piece of scrap paper before writing the formal proof. This is because with more complicated examples, I might have to constantly change my approach.