Theoretical Computer Science Cheat Sheet

Theoretical Computer Science Cheat Sheet
De nitions Series
f(n) = O(g(n)) i9 positive c; n0 such that
0  f(n)  cg(n) 8n  n0.
n
Xi=1
i = n(n + 1)
2 ;
n
Xi=1
i2 = n(n + 1)(2n + 1)
6 ;
n
Xi=1
i3 = n2(n + 1)2
4 :
In general:
n
Xi=1
im =
1
m + 1(n + 1)m+1 − 1 −
n
Xi=1