Asymptotics and Algorithm Efficiency Flashcards
1
Q
Stirling’s Approximation
A
Provides an approximation for n!: n! ≈ sqrt(2πn)*(n/e)^n
2
Q
h(n) ∈ O(f(n))
A
∃c, n0 such that ∀n>=n0, h(n) <= cf(n)
3
Q
h(n) ∈ Ω(f(n))
A
∃c, n0 such that ∀n>=n0, h(n) >= cf(n)
4
Q
h(n) ∈ Θ(f(n))
A
∃c0, c1, n0 such that ∀n>=n0, c0f(n) <= h(n) <= c1f(n)
(alternatively: h(n) ∈ O(f(n)) and h(n) ∈ Ω(f(n)))
5
Q
h(n) ∈ ω(f(n))
A
limit as n approaches infinity of h(n)/f(n) = ∞
6
Q
h(n) ∈ o(f(n))
A
limit as n approaches infinity of h(n)/f(n) = 0
7
Q
Order the following functions in increasing order of growth: n^2, 1, 2^n, n^n, log(n), n!, nlogn, (logn)!, 2^log(n), √n, log(n!)
A
1, log(n), √n, {n, 2^log(n)}, {nlogn, log(n!)}, n^2, 2^n, n!, n^n