Theoretical Computer Science Cheat Sheet

ADVERTISEMENT

Theoretical Computer Science Cheat Sheet
Definitions
Series
iff ∃ positive c, n
f (n) = O(g(n))
such that
0
n
n
n
2
2
n(n + 1)
n(n + 1)(2n + 1)
n
(n + 1)
0 ≤ f (n) ≤ cg(n) ∀n ≥ n
2
3
.
i =
,
i
=
,
i
=
.
0
2
6
4
i=1
i=1
i=1
iff ∃ positive c, n
f (n) = Ω(g(n))
such that
0
In general:
f (n) ≥ cg(n) ≥ 0 ∀n ≥ n
.
0
n
n
1
m
m+1
m+1
m+1
m
i
=
(n + 1)
1
(i + 1)
i
(m + 1)i
f (n) = Θ(g(n))
iff f (n) = O(g(n)) and
m + 1
i=1
i=1
f (n) = Ω(g(n)).
n 1
m
1
m + 1
f (n) = o(g(n))
iff lim
f (n)/g(n) = 0.
m
m+1 k
i
=
B
n
.
n→∞
k
m + 1
k
i=1
k=0
iff ∀ > 0, ∃n
lim
a
= a
such that
0
n
Geometric series:
n→∞
|a
a| < , ∀n ≥ n
.
0
n
n
n+1
c
1
1
c
|c| < 1,
i
i
i
c
=
,
c = 1,
c
=
,
c
=
,
least b ∈ R such that b ≥ s,
sup S
c
1
1
c
1
c
∀s ∈ S.
i=0
i=0
i=1
n
n+2
n+1
nc
(n + 1)c
+ c
c
greatest b ∈ R such that b ≤
|c| < 1.
i
i
inf S
ic
=
,
c = 1,
ic
=
,
2
2
(c
1)
(1
c)
s, ∀s ∈ S.
i=0
i=0
Harmonic series:
| i ≥ n, i ∈ N}.
lim inf
a
lim
inf{a
n
i
n
n
1
n(n + 1)
n(n
1)
n→∞
n→∞
H
=
,
iH
=
H
.
n
i
n
| i ≥ n, i ∈ N}.
i
2
4
lim sup
a
lim
sup{a
n
i
i=1
i=1
n→∞
n→∞
n
n
i
n + 1
1
n
Combinations: Size k sub-
H
= (n + 1)H
n,
H
=
H
.
i
n
i
n+1
k
m
m + 1
m + 1
sets of a size n set.
i=1
i=1
n
n
Stirling numbers (1st kind):
n
n!
n
n
n
k
1.
2.
n
3.
=
,
= 2
,
=
,
Arrangements of an n ele-
k
(n
k)!k!
k
k
n
k
k=0
ment set into k cycles.
n
n
n
1
n
n
1
n
1
4.
5.
=
,
=
+
,
n
Stirling numbers (2nd kind):
k
k
k
1
k
k
k
1
k
Partitions of an n element
n
n
m
n
n
k
r + k
r + n + 1
6.
7.
set into k non-empty sets.
=
,
=
,
m
k
k
m
k
k
n
k=0
n
1st order Eulerian numbers:
n
n
k
n + 1
r
s
r + s
k
8.
9.
Permutations π
π
. . . π
on
=
,
=
,
1
2
n
m
m + 1
k
n
k
n
{1, 2, . . . , n} with k ascents.
k=0
k=0
n
k
n
1
n
n
10.
11.
k
n
= ( 1)
,
=
= 1,
2nd order Eulerian numbers.
k
k
1
n
k
C
Catalan Numbers: Binary
n
n
n
n
1
n
1
n 1
12.
13.
= 2
1,
= k
+
,
trees with n + 1 vertices.
2
k
k
k
1
n
n
n
n
n
14.
15.
16.
17.
= (n
1)!,
= (n
1)!H
,
= 1,
,
n 1
1
2
n
k
k
n
n
n
1
n
1
n
n
n
n
1
2n
18.
19.
20.
21. C
= (n
1)
+
,
=
=
,
= n!,
=
,
n
k
k
k
1
n
1
n
1
2
k
n + 1
n
k=0
n
n
n
n
n
n
1
n
1
22.
23.
24.
=
= 1,
=
,
= (k + 1)
+ (n
k)
,
0
n
1
k
n
1
k
k
k
k
1
0
n
n
n + 1
1 if k = 0,
25.
26.
27.
n
n
n
=
= 2
n
1,
= 3
(n + 1)2
+
,
2
2
k
0 otherwise
1
n
m
n
n
x + k
n
n + 1
n
n
k
28. x
n
29.
n
k
30. m!
=
,
=
(m + 1
k)
( 1)
,
=
,
k
n
m
k
m
k
n
m
k=0
k=0
k=0
n
n
n
n
k
n
n
31.
32.
33.
n k m
=
( 1)
k!,
= 1,
= 0 for n = 0,
m
k
m
0
n
k=0
n
n
n
n
1
n
1
n
(2n)
34.
35.
= (k + 1)
+ (2n
1
k)
,
=
,
n
k
k
k
1
k
2
k=0
n
n
x
n
x + n
1
k
n + 1
n
k
k
36.
37.
n k
=
,
=
=
(m + 1)
,
x
n
k
2n
m + 1
k
m
m
k=0
k
k=0

ADVERTISEMENT

00 votes

Related Articles

Related forms

Related Categories

Parent category: Education
Go
Page of 10