Metric Unit Calculator
Computer Science · Data Sheet

Asymptotic Definitions and Finite Sums Cheat Sheet

SymbolConstantValueUnit
f(n) = O(g(n))Big OThere exist positive c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0formula
f(n) = Omega(g(n))Big OmegaThere exist positive c and n0 such that f(n) >= c*g(n) >= 0 for all n >= n0formula
f(n) = Theta(g(n))Big Thetaf(n) = O(g(n)) and f(n) = Omega(g(n))formula
f(n) = o(g(n))Little olim[n->infinity] f(n)/g(n) = 0formula
sum iArithmetic sumsum(i=1..n) i = n(n+1)/2formula
sum i^2Square sumsum(i=1..n) i^2 = n(n+1)(2n+1)/6formula
sum i^3Cube sumsum(i=1..n) i^3 = n^2(n+1)^2/4formula
sum c^iFinite geometric sumsum(i=0..n) c^i = (c^(n+1)-1)/(c-1), c != 1formula
sum c^iInfinite geometric sumsum(i=0..infinity) c^i = 1/(1-c), |c| < 1formula
sum from i=1Infinite shifted geometric sumsum(i=1..infinity) c^i = c/(1-c), |c| < 1formula
sum i*c^iFinite weighted geometric sumsum(i=0..n) i*c^i = (n*c^(n+2)-(n+1)*c^(n+1)+c)/(c-1)^2formula
sum i*c^iInfinite weighted geometric sumsum(i=0..infinity) i*c^i = c/(1-c)^2, |c| < 1formula
H_nHarmonic numberH_n = sum(i=1..n) 1/iformula
sum H_iHarmonic number sumsum(i=1..n) H_i = (n+1)H_n - nformula
C(n,k)Binomial coefficientC(n,k) = n!/((n-k)!k!)formula
sum C(n,k)Binomial row sumsum(k=0..n) C(n,k) = 2^nformula
C(n,k)Binomial symmetryC(n,k) = C(n,n-k)formula
C(n,k)Pascal identityC(n,k) = C(n-1,k) + C(n-1,k-1)formula
C_nCatalan numberC_n = C(2n,n)/(n+1)formula

About this calculator

A searchable formula reference transcribed and normalized from the supplied Theoretical Computer Science Cheat Sheet.

Asymptotic Definitions and Finite Sums formula reference

This searchable reference organizes formulas from the supplied Theoretical Computer Science Cheat Sheet into web-friendly notation. Use the search box to find a formula by name or symbol, then review its assumptions before applying it.

Some identities use conventional mathematical notation such as summation limits, factorials, congruences, expectations and asymptotic bounds. These entries are reference material and should be interpreted within their stated domains.