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𝑛 ≠ Θ (𝑛)
is 5𝑛 Θ(𝑛^2)
5𝑛 ≠ Θ(𝑛^2)
Multiplying and Adding with Big O
You will
𝑂 𝑓 𝑛 ⋅ 𝑂 𝑔 𝑛 = 𝑂(𝑓 𝑛 ⋅ 𝑔 𝑛 )
If 𝑓 𝑛 = 𝑂 𝑔 𝑛 , then
𝑂 𝑓 𝑛 + 𝑂 𝑔 𝑛 = 𝑂(𝑔 𝑛 ).
a^m
a….a
m times
a^-m
1/a^m
a^ma^n
a^m+n
(a^m)^n
a^mn
a^m/a^n
a^m-n
loga(xy)
loga(x) + loga(y)
a^loga(xy)
xy= a^loga(x)*a^loga(y) = a^logax+loga(y)
loga(x^n)
n*loga(x)
a^log(x^n)
x^n = (a^logax)^n = a^nlogax
log(x/y)
loga(x) - loga(y)
a^loga(x/y)
x/y = a^logax/a^logay = a^logax-logay
change log to base b from base a
