Week 10: Big-Omega, big-Theta, general properties

big-Ω proof
similar to big-O proof but
choose Magic Breakpoint B = 1,
then we can assume n ≥ 1
under-estimation tricks
➔ remove a positive term
◆ 3n² + 2n ≥ 3n²
➔ multiply a negative term
◆ 5n² - n ≥ 5n² - nxn = 4n²
over-estimation tricks
➔ remove a negative term
◆ 3n² - 2n ≤ 3n²
➔ multiply a positive term
◆ 5n² + n ≤ 5n² + nxn = 6n²

big-O proofs for general functions
1.If f grows no faster than g,
and g grows no faster than h,
then f must grow no faster than h.
2. nobody can write halt(f,n)
3. Reductions
If function f(n) can be implemented by
extending another function g(n),
then we say f reduces to g
def f(n):
 return g(2n)
g computable f computable =>
f non-computable g non-computable