We're learning more about Big-Oh and its proofs. With these proofs, I think it's not hard to follow through with a bit more practice. However, it was in the previous lessons with analysing algorithms and counting steps that confused me most. Seeing the sigma and all these other complicated notation was really frightening and I think I will need more clarification on that part.
I have been learning a lot from Instructor Larry Zhang's lecture slides and I think his notes are very helpful and easy to comprehend.
Big-Oh's definition is that if a function a is in the Big-Oh of another function, b, it simply means that cb will grow faster than a after a certain point, and cb will become the upper bound of a, where c is a wisely chosen constant.
For a f(n) in O(n²) the formal definition is
∃c ϵ R⁺, ∃B ϵ N, ∀n ϵ N, n ≥ B ⇒ f(n) ≤ cn²
For Big-Oh proofs, the structure starts off all very similarly. Choose a c and a B and make sure it works with n. For more complex proofs, such as higher degree polynomials, we overestimate the left and underestimate the right. For non-polynomial functions such as 2^n, we have to use the definition of a limit to prove Big-Oh.
Big-Omega is the reverse of Big-Oh. It's saying that there is a lower bound cb to a. We now have to pick a c small enough to make the right side a lower bound.
Then we have general statements about Big-Oh. We're now proving the case for a set of functions. For example, in Wednesday's lecture, we touched on proving the statement
∀ f, g, h ϵ F, (f ϵ O(g) Λ g ϵ O(h)) ⇒ f ϵ O(h)
No comments:
Post a Comment