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

Week 9: Big-Oh of polynomials, non-polynomials, limits

exercises of big-Oh proofs
 To prove polynomials: it’s all about picking c and B
   ➔ tip 1: c should probably be larger the
   constant factor of the highest-order term
   ➔ tip 2: see what happens when n = 1
   ➔ upper-bound the left
   side by overestimating
   ➔ lower-bound the right
   side by underestimating
   ➔ choose a c that connects
   the two bounds
To disprove, we prove the negation is true!
summary
➔ the ways we talked about of picking c and
B, the main point of them is that we know
how to show the bounding relation when
picking in these ways.
➔ these are not the only ways, you can be
more flexible when you are more familiar
with these types of proofs.
➔ In general, larger c or larger B don’t hurt

 prove big-Oh using limit techniques
to prove non polynomials we use limits - limit = infinity defined by
for all c in positive real number, there exist n' in natural number, for all natural number n bigger than n', the limit > c.
we take the limit of the f(n)/g(n) when evaluating f(n) in O(g(n)) for example, use limit rule above to show fn>cgn (fn/gn > c)
use L'Hopital's rule
lim fn/gn = f'n/g'n

Week 8: Counting steps, worst-case, formal big-Oh

Some others things about proofs
proof for statement with multiple quantifiers
∀x ∈ X, ∃y ∈ Y, ∀z ∈ Z, ∃w ∈ W, P => Q
      assume generic x ∈ X
          pick some y ∈ Y
              assume generic z ∈ Z
                  pick some w ∈ W
                      assume P
                           …
                           then Q
                      then P => Q
                  then ∃w ∈ W, P => Q
             then ∀z ∈ Z, ∃w ∈ W, P => Q
         then ∃y ∈ Y, ∀z ∈ Z, ∃w ∈ W, P => Q
     then ∀x ∈ X, ∃y ∈ Y, ∀z ∈ Z, ∃w ∈ W, P => Q

How to prove a = b ?

➔ Prove (a ≤ b) ∧ (a ≥ b)

How to prove a = b ?

➔ Prove (a ≤ b) ∧ (a ≥ b)

When the statement seems kind-of trivial but 

proving directly looks messy

➔ try contradiction

Back to Algorithms

formal definition of O, Ω
a function f(n) is in O(n) iff there exist c in positive real number, there exist B in natural number, such that for all natural number bigger than B, f(n) less or equal to cn. (f(n) grows slower than n)
➔ when finding upper-bound, it is OK to
over-estimate the number of steps
a function f(n) is in Ω(n) iff there exist c in positive real number, there exist B in natural number, such that for all natural number bigger than B, f(n) greater or equal to cn. (f(n) grows faster than n)
memorize the formulas! 

➔ when finding lower-bound, it is OK to
under-estimate the number of steps