Asymptotics and Algorithm Efficiency

Question 1

Stirling’s Approximation

Answer 1

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

Question 2

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

Answer 2

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

Question 3

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

Answer 3

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

Question 4

h(n) ∈ Θ(f(n))

Answer 4

∃c0, c1, n0 such that ∀n>=n0, c0f(n) <= h(n) <= c1f(n)
(alternatively: h(n) ∈ O(f(n)) and h(n) ∈ Ω(f(n)))

Question 5

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

Answer 5

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

Question 6

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

Answer 6

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

Question 7

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!)

Answer 7

1, log(n), √n, {n, 2^log(n)}, {nlogn, log(n!)}, n^2, 2^n, n!, n^n