Asymptotics and Algorithm Efficiency Flashcards

1
Q

Stirling’s Approximation

A

Provides an approximation for n!: n! ≈ sqrt(2πn)*(n/e)^n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

h(n) ∈ O(f(n))

A

∃c, n0 such that ∀n>=n0, h(n) <= cf(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

h(n) ∈ Ω(f(n))

A

∃c, n0 such that ∀n>=n0, h(n) >= cf(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

h(n) ∈ ω(f(n))

A

limit as n approaches infinity of h(n)/f(n) = ∞

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

h(n) ∈ o(f(n))

A

limit as n approaches infinity of h(n)/f(n) = 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly