Proofs have returned!

Prof. Heap introduced a notation that represent functions that take in a natural number and return a non-negative real number. The notation is ƒ: ℕ →ℝ ^≥0. In the lecture this week I learned how to prove 3n²+2n∈O(n²). ∃c∈ℝ+, ∃B∈ℕ, ∀n∈ℕ, n≥B ⇒ f(n)≤cn². To prove that statement we would have to find equations larger than 3n²+2n which is f(n) and equations less than or equal to cn². Then the equations would have to be linked proving 3n²+2n≤cn².

I also learned how to prove n³∉ O(3n²). First the standard thing to do is to negate the statement and then prove the negation. We want to make n³>c3n². This occurs when n>c3=3c. So we have to make n>3c and n≥B. So the statement in the proof would be, pick n>max(3c, B). Additionally a larger c or B doesn’t hurt, since it still proves n³∉ O(3n²) and it is only an approximation.

How to figure out what is big-Oh of who turned out to be pretty simple between polynomials. You only have to look at the highest degree term. The function with the larger or same degree is the big-Oh. In other words f(n) is in O(g(n)) exactly when the highest-degree term of f(n) is no larger than the highest-degree term of g(n).