Metric Unit Calculator
Computer Science · Data Sheet

Trees, Recurrences and Generating Functions Cheat Sheet

SymbolConstantValueUnit
|E|Tree edge countEvery tree with n vertices has n-1 edgesformula
sum 2^-d_iKraft inequalitysum(i=1..n) 2^(-d_i) <= 1formula
T(n)=aT(n/b)+f(n)Master theorem case 1If f(n)=O(n^(log_b(a)-epsilon)), then T(n)=Theta(n^log_b(a))formula
T(n)=aT(n/b)+f(n)Master theorem case 2If f(n)=Theta(n^log_b(a)), then T(n)=Theta(n^log_b(a)*log n)formula
T(n)=aT(n/b)+f(n)Master theorem case 3If f(n)=Omega(n^(log_b(a)+epsilon)) and a*f(n/b)<=c*f(n), then T(n)=Theta(f(n))formula
G(x)Ordinary generating functionG(x) = sum(i=0..infinity) g_i*x^iformula
g_(i+1)=2g_i+1Generating function recurrence exampleG(x) = x/((1-x)(1-2x))formula
g_iGenerating function coefficientFor G(x)=x/((1-x)(1-2x)), g_i=2^i-1formula
F_nFibonacci recurrenceF_n = F_(n-1)+F_(n-2), F_0=F_1=1formula
F_nBinet formulaF_n = (phi^(n+1)-phi_hat^(n+1))/sqrt(5) for F_0=F_1=1formula
F_(n+1)F_(n-1)-F_n^2Cassini identityF_(n+1)F_(n-1)-F_n^2 = (-1)^nformula
F_(n+k)Fibonacci additionF_(n+k)=F_k*F_(n+1)+F_(k-1)*F_nformula

About this calculator

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

Trees, Recurrences and Generating Functions 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.