Entry #6

We finally got to the topic of counting running time.  Previously in CSC165, we learned how to express with symbols, logics and proof with mathematical background. This week I studied about Big O which is about growth rate. Big O is the symbol that computer scientists use to show the upper bound of function's step. In other words, it is the maximum steps that a function can reach(over-estimation). In symbolic form, it looks like this.

At the first glance, it looked so cryptic and I had no idea what this statement was all about. I have a tendency to get discouraged when I see bunch of symbols that forms a statement. With Danny's help, I could figure out what this statement is all about although it took me some time. First, I looked at statement by parts.
first part is saying that takes natural number as input and returns positive real number. There is constant c which is positive real number and B a natural number that for all n if n is greater than B f(n) is equal or smaller than c * n^2 . B is the natural number that is n's minimum in this statement, and c is the multiplier that makes f(n) always smaller  c *(n^2).

When Proving Big O, proof structure looks like this.

Let c = __
Let B = __
Assume n ∈ N
     Assume n >= B
           Then f(n)
                  .
                  .    #playing around number until I get f(n) <= cn^2

          Then f(n) <= cn^2
     Then n>= B  -> f(n) <= cn^2
Then  ∃ c ∈ R+    ∃ B ∈ N     ∀n ∈ N    n>=B  -> f(n) <= cn^2