Introduction

Outline of Algorithmics

Exponent rule

(ab)c=abc\begin{gather*} (a^b)^c = a^{bc} \end{gather*}

Log rule

cloga(n)=nloga(c)\begin{gather*} c^{\log_a(n)} = n^{\log_a(c)} \end{gather*}

Asymptotics

Name
Notation
Rough Meaning
Definition
In-fix Notation

big-Oh

g=O(f)g=O(f)

gfg \le f

(C>0)[Cfg0(e.v.)](\exists C > 0)[C f \ge g \ge 0(e.v.)]

gfg \preceq f

big-Omega

g=Ω(f)g=\Omega(f)

gfg \ge f

(C>0)[Cgf0(e.v.)](\exists C > 0)[C g \ge f \ge 0(e.v.)]

gfg \succeq f

Theta

g=Θ(f)g=\Theta(f)

g=fg = f

(C>1)[C2fCg0(e.v.)](\exists C > 1)[C^2 f \ge C g \ge 0(e.v.)]

gfg \asymp f

small-oh

g=o(f)g=o(f)

gfg \ll f

(C>0)[Cfg0(e.v.)](\forall C > 0)[C f \ge g \ge 0(e.v.)]

gfg \ll f

small-omega

g=ω(f)g=\omega(f)

gfg \gg f

(C>0)[Cgf0(e.v.)](\forall C > 0)[C g \ge f \ge 0(e.v.)]

gfg \gg f

Stirling's Approximation

Original:

2πn(ne)ne112n+1<n!<2πn(ne)ne112n\sqrt{2\pi n}({n \over e})^n e^{1\over{12n + 1}} < n! < \sqrt{2\pi n}({n \over e})^n e^{1\over{12n}}

log(n!)=nlog(n)n+Θ(log(n))log(n!) = n \log(n) - n + \Theta(\log(n))

Further simplification:

log(n!)=Θ(nlog(n))log(n!) = \Theta(n \log(n))

A possible transformation:

n!=Θ(enlog(n))n! = \Theta(e^{n \log(n)})

Comparison Tree

Example: Merge x1<x2x_1 < x_2 and y1<y2<y3<y4y_1 < y_2 < y_3 < y_4.

Hasse Diagram

The lower the smaller, circle(o) for x, cross(×) for y.

Last updated