Asymptotics Flashcards
1
Q
What happens if f(n) is an element of little o(g(n))?
A
then f(n) is in O(g(n)) but NOT in big Omega(g(n)).
2
Q
What happens if f(n) is in little omega(g(n))?
A
then f(n) is in Big Omega(g(n)) but NOT in big O(g(n)).
3
Q
What is the definition of f(n) being in big O(g(n))?
A
There exist constants c>0 and n_o (natural number) s.t for all n>N_o,
f(n) <= cg(n).
4
Q
What is the definition of f(n) being in Big Omega?
A
There exist constants c>0 and n_o (natural number) s.t for all n>N_o,
f(n) >= cg(n).
5
Q
if lim ₓ→∞ f(n)/g(n) =0 then
A
f(n) ∈ o(g(n)) i.e f(n) ∈ O(g(n)) and NOT f(n) ∈ Ω(g(n)).
6
Q
If lim ₓ→∞ f (n)/g(n) = ∞ then
A
f(n) ∈ ω(g(n)).
7
Q
If lim ₓ→∞ f(n)/g(n) = c>0 then
A
f(n) ∈ θ(g(n))
8
Q
A
