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!
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
under-estimate the number of steps
No comments:
Post a Comment