Theoretical Computer Science Cheat Sheet
ADVERTISEMENT
1
2
3
4
5
6
7
8
9
10Theoretical Computer Science Cheat Sheet
Definitions
Series
iff ∃ positive c, n
f (n) = O(g(n))
such that
∑
∑
∑
n
n
n
0
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
n
0
Geometric series:
n→∞
|a
a| < ϵ, ∀n ≥ n
.
∑
∑
∞
∑
∞
n
0
n
n+1
c
1
1
c
i
c ̸ = 1,
i
i
|c| < 1,
c
=
,
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,
|c| < 1.
i
i
inf S
ic
=
,
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
n→∞
n→∞
1
n(n + 1)
n(n
1)
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
n
1.
=
,
2.
= 2
,
3.
=
,
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
k
n
10.
= ( 1)
,
11.
=
= 1,
2nd order Eulerian numbers.
k
k
1
n
k
{
}
{
}
{
}
{
}
C
Catalan Numbers: Binary
n
n
n
n
1
n
1
n 1
12.
= 2
1,
13.
= k
+
,
trees with n + 1 vertices.
2
k
k
k
1
[
]
[
]
[
]
[
]
{
}
n
n
n
n
n
≥
14.
= (n
1)!,
15.
= (n
1)!H
,
16.
= 1,
17.
,
n 1
1
2
n
k
k
[
]
[
]
[
]
{
}
[
]
(
)
[
]
(
)
∑
n
n
n
1
n
1
n
n
n
n
1
2n
18.
= (n
1)
+
,
19.
=
=
,
20.
= n!,
21. C
=
,
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.
=
= 1,
23.
=
,
24.
= (k + 1)
+ (n
k)
,
0
n
1
k
n
1
k
k
k
k
1
⟨
⟩
⟨
⟩
⟨
⟩
(
)
{
0
n
n
n + 1
1 if k = 0,
n
n
n
25.
=
26.
= 2
n
1,
27.
= 3
(n + 1)2
+
,
k
0 otherwise
1
2
2
⟨
⟩(
)
⟨
⟩
(
)
{
}
⟨
⟩(
)
∑
∑
∑
n
m
n
n
x + k
n
n + 1
n
n
k
n
n
k
28. x
=
,
29.
=
(m + 1
k)
( 1)
,
30. m!
=
,
k
n
m
k
m
k
n
m
⟨
⟩
{
}(
)
⟨ ⟨
⟩ ⟩
⟨ ⟨
⟩ ⟩
k=0
k=0
k=0
∑
n
n
n
n
k
n
n
= 0 for n ̸ = 0,
n k m
31.
=
( 1)
k!,
32.
= 1,
33.
m
k
m
0
n
⟨ ⟨
⟩ ⟩
⟨ ⟨
⟩ ⟩
⟨ ⟨
⟩ ⟩
⟨ ⟨
⟩ ⟩
k=0
∑
n
n
n
n
1
n
1
n
(2n)
34.
= (k + 1)
+ (2n
1
k)
,
35.
=
,
n
k
k
k
1
k
2
{
}
⟨ ⟨
⟩ ⟩(
)
{
}
(
){
}
k=0
{
}
∑
∑
∑
n
n
x
n
x + n
1
k
n + 1
n
k
k
n k
36.
=
,
37.
=
=
(m + 1)
,
x
n
k
2n
m + 1
k
m
m
k=0
k
k=0
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education