9th week journal

This week, we are doing the actual proofs for big O and big omega. Since the definition of big-O is beyond a certain breakout point B, a function f(n) is upper-bounded by cg(n). We use some techniques to prove the function belongs to big-oh. O g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≤ c·g(n)} For polynomial, we first need to look at the highest degree of the function and the relation of inequality to find certain c. In order to do this, we need to analyze if there is any function that will be certainly larger than the function by adding one more degree. To see if a function is belongs to big-oh function, we just need to compare the highest degree. If the function's degree is smaller than the big-oh function's degree, then it is in big-O.Some proofs are more complicated and it requires us to approach it from the top to bottom and bottom to the top at the same time, then they will reach at a certain time that we need to determine c at that time.  Big-omega is the lower bound, meaning the f(n) is lower-bounded by cg(n). Ω g(n) = {f : ℕ à ℝ^≥0| ∃c ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ f(n) ≥ c·g(n) } For theta, we need to set two bounds. Choose the upper-bound to overestimate the function that we are proving, and choose the lower-bound to underestimate the function. θ g(n) = {f : ℕ à ℝ^≥0| ∃c1, c2 ∈ ℝ⁺, ∃B ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ c2 g(n)≤f(n)≤c1·g(n)}And we can choose c to connect these two bounds. For non-polynomial, we use the math tool, limit. First, we need to use L'Hopital's rule to define the limits of these two functions are approaching infinity when n increases. Then we need to translate it into its definition then relate it to the definition of big-oh.

This week material is also about proofs. But I found these proofs are easier than the proofs we learnt before. We can justify it easily and prove it using definition of big-oh and finding bounds. I need more practices of the general proofs because I found the midterm is quite hard. I think I didn' t do that well in this midterm, but I wrote all the structures, hope I can get some marks for that. More practice will make myself get more familiar with different techniques and think more quickly, especially during the test. Sometimes, I know the thoughts but I find difficult to use the definitions to prove it.