Basic Analysis Flashcards
inverses addition and subtraction
𝑥 + 𝑎 − 𝑎
𝑥 − 𝑎 + 𝑎
x
inverses multiplication and division
(𝑥 ⋅ 𝑎)/𝑎
(𝑥/𝑎) ⋅ 𝑥
x
Inverses Logarithms
a^loga(x)
loga(a^x)
x
Definition Big O
f(n) = O(g(n)) if there exist positive constants n0 and c such that for all n >_n0 f(n) <= c g(n) informally f is eventually at most a constant multiple of g
Proof that n = O(n^2)
For all 𝑛 ≥ 1, 𝑛 ≤ 1 ⋅ 𝑛^2 (divide both sides by n get 1<= n)
Proof 2𝑛 + 8 = 𝑂(n^2)
For all 𝑛 ≥ 4, 2𝑛 + 8 ≤ 1 ⋅ 𝑛^2. (subtract 2n -8 from both sides, get n^ - 2n - 8 >= 0 (n+2)(n-2) >=0)
proof 2𝑛 + 8 = 𝑂 (𝑛)
For all 𝑛 ≥ 8, 2𝑛 + 8 ≤ 3 ⋅ 𝑛. (subtract 2ns from both sides, get 8<=n)
𝑛” ≠ 𝑂(𝑛)
No matter how you choose 𝑐 and 𝑛0, I can find an 𝑛 ≥ 𝑛! such that
𝑛^2 > 𝑐 ⋅ 𝑛.
big omega of 𝑔(𝑛)”)
Definition: 𝑓 𝑛 = Ω 𝑔 𝑛 (“𝑓(𝑛) is big omega of 𝑔(𝑛)”) if
𝑔 𝑛 = 𝑂 𝑓 𝑛 .
big theta of 𝑔(𝑛)”)
Definition: 𝑓 𝑛 = Θ(𝑔 𝑛 ) (“𝑓(𝑛) is big theta of 𝑔(𝑛)”) if
𝑓 𝑛 = 𝑂 𝑔 𝑛 and 𝑔 𝑛 = 𝑂(𝑓 𝑛 ).
is 5𝑛 Ω(𝑛)?
5𝑛 = Ω(𝑛)
is 𝑛! + 3𝑛 Ω(𝑛)
𝑛! + 3𝑛 = Ω( 𝑛)
is 5𝑛 Ω(𝑛!)
5𝑛 ≠ Ω(𝑛!)
is 5𝑛 Θ(𝑛)?
5𝑛 = Θ(𝑛)
is 𝑛! + 3𝑛 Θ (𝑛)?
𝑛! + 3𝑛 ≠ Θ (𝑛)
