Week 9: Big- Oh Proofs

In this week of lecture we learned how to prove using the definition of Big-Oh.

Using the definition, the basic concept to grasp is finding a c and B, that past the threshold B, the definition holds. Even with a constant, we let n=1 and calculate the value. For example, to prove 3n^2+2n+5 is in O(n^2), we let n=1, so the function calculates to 10. We let c=10, and B=1. For all n>1, 10n^2 will be greater than the function, so it holds.

For more complex O and functions, we meet the two in the centre. We overestimate the function, and underestimate the O. For example, for function 7n^6-5n^4+2n^3 <= 7n^6+2n^3 <= 7n^6+2n^6 = 9n^6. Vice versa for underestimating.

In order to disprove, we just prove the negation. This also involves picking a smart B and c value.

For non-polynomials, we prove using limits. To find a function not in a bigoh: We find a breakpoint n' so that for n>n', function/bigohfunction > c. That is, that beyond a threshold, the function is always bigger than the bigohfunction.