10th week journal

I found that other slogs are very interesting. Some of the people gave out really detailed summary of the lecture. Like Celina, (link: http://celinasopiniononcsc165.blogspot.ca/), she always gave out examples, and I found it useful to me too! And they usually have some interesting names for their posts too. This week was an extension of big-O, big-omega proofs. We were proving the general case about big-O and big-omega. We are considering not any specific function but all the functions. For proving general cases, we need to think according to the definitions of big-O and big-omega. We first need to understand the statement. For definition of big-O, O g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≤ c·g(n)}, it means that f grows no faster than g. For definition of big-omega, Ω g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≥ c·g(n)}, it means that f grows faster than g. I usually find that it is easier to understand it to translate it into English words and draw a graph of it. And I found that proving that there exists certain functions is in big-O or big-Omega was harder than proving for all the functions, with certain properties.  Because it's hard to come up different equations, and the proofs are not as straight forward as the other cases. 

We finished up the materials about big-O and big-Omega. To conclude, we learnt three parts of the big-O proofs. Proofs for polynomials, proofs for non-polynomials and proofs for general big-O statement. For polynomials, we just need to know the definitions and start overestimate and underestimate the functions. For non-polynomials, we use limits. For general proofs, we need to pick B and c based on known B's and c's.