WEEK 8 JOURNAL: BIG O PROBLEMS

    This week, we we talked about the formal definition of O and Ω, and we learned how to prove a function is in O. The definition for O is that ∃c∈ℝ+,∃b∈ℕ,∀n∈ℕ,n≥b => f(n) ≤ cg(n). This definition means that after a break point "b", f is always smaller than g. Conversely, Ω means that after the break point "b", f is always bigger than Ω. Therefore the definition of Ω is that ∃c∈ℝ+,∃b∈ℕ,∀n∈ℕ,n≥b => f(n) ≥ cg(n).
    To prove a function is in O, we need to find a suitable c such that f(n) ≤ cg(n). For example, in class we talked about how to prove the worst case complexity of insertion sort is in O(n^2). To solve this question, we can pick n = 10 then Wis = (3/2)n^2 + (9/2)n - 4 ≤ 10n^2. Next, we pick a b ≤ 10. Therefore, we proved that Wis is in O.