Introduction
Outline of Algorithmics
Exponent rule
(ab)c=abc Log rule
cloga(n)=nloga(c) Asymptotics
Name
Notation
Rough Meaning
Definition
In-fix Notation
(∃C>0)[Cf≥g≥0(e.v.)]
(∃C>0)[Cg≥f≥0(e.v.)]
(∃C>1)[C2f≥Cg≥0(e.v.)]
(∀C>0)[Cf≥g≥0(e.v.)]
(∀C>0)[Cg≥f≥0(e.v.)]
Stirling's Approximation
Original:
2πn(en)ne12n+11<n!<2πn(en)ne12n1
log(n!)=nlog(n)−n+Θ(log(n))
Further simplification:
log(n!)=Θ(nlog(n))
A possible transformation:
n!=Θ(enlog(n))
Comparison Tree
Example: Merge x1<x2 and y1<y2<y3<y4.
Hasse Diagram
The lower the smaller, circle(o) for x, cross(×) for y.