CS Notation

Part 6 of 8 · Previous: Sequences · Index · Next: Proofs

25. Common symbols used in algorithms

Symbol	Common meaning
$n$	Input size
$k$	Count, parameter, or iteration number
$i, j$	Indices
$T (n)$	Running time
$S (n)$	Space consumption
$G = (V, E)$	Graph
$w (e)$	Weight of edge $e$
$d (v)$	Distance to vertex $v$
$π (v)$	Parent/predecessor of $v$
$\infty$	Infinity or unreachable initial distance
$⊥$	Undefined, false, failure, or bottom value
$⊤$	True or top value
$ε$	Empty string or a small positive value
$λ$	Parameter, eigenvalue, or anonymous function
$δ$	Difference, transition function, or small change
$Δ$	Larger change, discriminant, or maximum degree
$μ$	Mean or parameter
$σ$	Standard deviation or alphabet
$Σ$	Alphabet or named set

Note

Symbols are overloaded. Their meaning comes from their definition in the paper.

Notation	Meaning
$Σ$	Alphabet
$ε$	Empty string
$Σ^{*}$	All finite strings over $Σ$
$Σ^{+}$	All nonempty finite strings
$	w
$uv$	Concatenation of strings
$L \subseteq Σ^{*}$	Language over alphabet $Σ$
$w \in L$	String $w$ belongs to language $L$
$L^{*}$	Kleene closure
$L_{1} L_{2}$	Concatenation of two languages
$L_{1} \cup L_{2}$	Union of languages

Example:

Σ = {a, b}

Σ^{*} = {ε, a, b, aa, ab, ba, bb, \dots}

Notation	Meaning
$e : τ$	Expression $e$ has type $τ$
$Γ ⊢ e : τ$	Under environment $Γ$ , $e$ has type $τ$
$Γ, x : τ$	Environment extended with variable $x$ of type $τ$
$e \to e^{'}$	$e$ reduces/evaluates one step to $e^{'}$
$e \to^{*} e^{'}$	Zero or more evaluation steps
$λ x . e$	Anonymous function taking $x$ and returning $e$
$τ_{1} \to τ_{2}$	Function type
$τ_{1} \times τ_{2}$	Product/pair type
$\forall α . τ$	Polymorphic type

\frac{Γ ⊢ e _{1} : τ _{1} Γ ⊢ e _{2} : τ _{2}}{Γ ⊢ ( e _{1} , e _{2} ) : τ _{1} \times τ _{2}}

Read:

If the statements above the line are true, then the statement below the line follows.