Closed form for n!
Factorial defines a product: n
n ! :: = 1 ⋅ 2 ⋅ 3 ⋅⋅⋅ (n − 1) ⋅ n = ∏ i
i =1
Stirling’s formula, Turn product into a sum taking logs:
Asymptotics ln(n!) = ln(1 · 2 · 3 · · · (n – 1) · n)
= ln 1 + ln 2 + · · · + ln(n – 1) + ln(n)
n
= ∑ ln(i )
i =1
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.1 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.2
Integral Method Integral Method
n
Integral Method to bound ∑ ln i
i =1
Bounds on ln(n!)
n n n
ln n
… ln (x+1)
ln (x) ∫ ln(x) dx · ∑ ln(i) · ∫ ln (x+1)dx
ln 5 1 i=1 0
ln 4
ln 3 ln ln n
ln 2 ln 5 n-1
ln 3 ln 4
ln 2
1 2 3 4 5 n–2 n–1 n
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.3 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.4
Integral Method Integral Method
Reminder:
⎛ x⎞ Bounds on ln(n!)
∫ ln x dx = x ln ⎜ ⎟=
⎝e⎠
n
∫ ln(x) dx · ∑ ln(i) · ∫ ln (x+1)dx
n n
1 i=1 0
n ln (n/e) +1 · ∑ ln(i) · (n+1) ln((n+1)/e) +1
n
1 ⎛n⎞
So guess: ∑ ln(i) ≈ (n + 2 )ln ⎜⎝ e ⎟⎠
i =1
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.5 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.6
Integral Method Stirling’s Formula
n
1 ⎛n⎞
∑ ln(i) ≈ (n + 2 )ln ⎝⎜ e ⎠
⎟
i=1
A precise approximation:
n
exponentiating:
⎛n⎞
n! ~ 2π n ⎜ ⎟
n ⎝e⎠
⎛n⎞
n! ≈ n / e ⎜ ⎟
⎝e⎠
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.7 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.8
Asymptotic Equivalence Stirling’s Formula
Def. f(n) ~ g(n)
n
⎛n⎞
iff f ( n)
n! ~ 2π n ⎜ ⎟
lim =1 ⎝e⎠
n→∞ g ( n)
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.9 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.10
Asymptotic Equivalence Little Oh
Example: Asymptotically smaller:
because Def. f(n) = o(g(n))
iff f ( n)
lim =0
n→∞ g ( n)
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.11 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.15
2
Little Oh Big Oh
Asymptotic Order
of Growth:
because f(n) = O(g(n))
⎛ f ( n) ⎞
lim sup ⎜ ⎟<∞
n →∞ ⎝ g ( n ) ⎠
a technicality -- ignore now
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.16 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.17
Big Oh The Oh’s
because If f = o(g) or f ~ g then f = O(g)
lim = 0 lim = 1 lim < ∞
converse is NOT true!
=3<∞
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.18 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.19
The Oh’s Big Oh
Equivalent definition:
If f = o(g), then g ≠ O(f) f(n) = O(g(n))
g
lim f = 0 lim =∞
g f ∃c,n0 ≥ 0 ∀n ≥ n0 |f(n)| ≤ c·g(n)
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.20 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.21
3
Big Oh
f(x) = O(g(x))
blue stays c· g(x)
below red
Problems 1, 2
f(x)
no
Copyright © Albert Meyer, 2003. October 16, 2003 L7-2.22 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.23
Little Oh Little Oh
Lemma: xa = o(xb) for a < b Lemma: ln x = o(xδ) for δ > 0.
Proof: x a Proof: 1
1 ≤ y for y ≥1.
= and b - a > 0. y
x b−a
xb z 1 z
So as x → ∞, ∫ 1 y
dy ≤ ∫ 1
ydy
1
xb-a → ∞ and b − a → 0 . z2 −1
x ln z ≤
2
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.24 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.25
Little Oh Theta
Same Order of Growth:
Lemma: ln x = o(xδ) for δ > 0.
z 2
f(n) = Θ(g(n))
Proof:
ln z ≤(cont’d)
Let z ::= x ε
2
ε ln x xε f(n) = O(g(n)) and g(n) = O(f(n))
≤
2 2
xε Not the same as “ ~ “ !
ln x ≤ = o( xδ ) for δ > ε.
ε
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.26 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.28
Big Oh Mistakes Big Oh Mistakes
f = O(g) defines a relation “= O(·)”
Lower bound blunder:
Don’t write O(g) = f.
Otherwise: x = O(x), so O(x) = x.
“f is at least O(n2)”
But 2x = O(x), so
2x = O(x) = x,
therefore 2x = x.
Nonsense!
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.29 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.30
Big Oh Mistakes Big Oh Mistakes
n n
False Lemma:
∑ i = O(n) False Lemma: ∑ i = O(n)
i=1
i=1
False Proof:
n
Of course really ∑ i = θ(n 2
) 0 = O(1), 1 = O(1), 2 = O(1),…
i=1 So each i = O(1). So
∑ i = =O(1)
i=1
+ O(1) + ⋅ ⋅ ⋅ + O(1)
n· O(1) = O(n).
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.31 Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.32
Team Problems
Problems
3 & 4
Copyright © Albert Meyer and Ronitt Rubinfeld, 2005. October 31, 2005 L9-1.33
