Special cases.

[saga.git] / notation.tex

diff --git a/notation.tex b/notation.tex
index 1f74341d0ae532c45f561cdccd75e730b2e171a3..f2c84dd1ec0bf08c0817028aa0e55ef6d2ded9e1 100644 (file)
--- a/notation.tex
+++ b/notation.tex
@@ -6,10 +6,15 @@
 
 {\obeylines\parskip=0pt
 \def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2}
-\def\[#1]{[\ref{#1}]}
+\def\[#1]{~{\it(\ref{#1})}}
 \n{$\bb R$}{the set of all real numbers}
 \n{$\bb N$}{the set of all natural numbers, including 0}
 \n{${\bb N}^+$}{the set of all positive integers}
+\n{$\O(g)$}{asymptotic~$O$: $f=\O(g)$ iff $\exists c>0: f(n)\le g(n)$ for all~$n\ge n_0$}
+\n{$\Omega(g)$}{asymptotic~$\Omega$: $f=\Omega(g)$ iff $\exists c>0: f(n)\ge g(n)$ for all~$n\ge n_0$}
+\n{$\Theta(g)$}{asymptotic~$\Theta$: $f=\Theta(g)$ iff $f=\O(g)$ and $f=\Omega(g)$}
+\n{$\widetilde\O(g)$}{$f=\widetilde\O(g)$ iff $f=\O(g\cdot\log^{\O(1)} g)$}
+\n{$\poly(n)$}{$f=\poly(n)$ iff $f=\O(n^c)$ for some $c$}
 \n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
 \n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
 \n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
@@ -47,7 +52,9 @@
 \n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]}
 \n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]}
 \n{$x[i]$}{when $x\in{\bb N}$: the value of the $i$-th bit of~$x$ \[bitnota]}
+\n{$x[B]$}{when $x\in{\bb N}$: the values of the bits at positions in the set~$B$ \[qhnota]}
 \n{$\pi[i]$}{when $\pi$ is a~sequence: the $i$-th element of~$\pi$, starting with $\pi[1]$ \[brackets]}
+\n{$\pi[i\ldots j]$}{the subsequence $\pi[i], \pi[i+1], \ldots, \pi[j]$}
 \n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
 \n{$\0$, $\1$}{bits in a~bit string \[bitnota]}
 \n{$\equiv$}{congruence modulo a~given number}
@@ -60,7 +67,6 @@
 \n{$\bxor$}{bitwise non-equivalence: $(x\bxor y)[i]=1$ iff $x[i]\ne y[i]$}
 \n{$x \shl n$}{bitwise shift of~$x$ by $n$~positions to the left: $x\shl n = x\cdot 2^n$}
 \n{$x \shr n$}{bitwise shift of~$x$ by $n$~positions to the right: $x\shr n = \lfloor x/2^n \rfloor$}
-\n{$\prec$}{an~arbitrary linear order}
 \n{$R_{C,\prec}(x)$}{the rank of~$x$ in a~set~$C$ ordered by~$\prec$ \[rankdef]}
 \n{$R^{-1}_{C,\prec}(i)$}{the unrank of~$i$: the $i$-th smallest element of a~set~$C$ ordered by~$\prec$ \[rankdef]}
 \n{$[n]$}{the set $\{1,2,\ldots,n\}$ \[pranksect]}
@@ -70,6 +76,12 @@
 \n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]}
 \n{$K_k$}{the complete graph on~$k$ vertices}
 \n{$C_k$}{the cycle on~$k$ vertices}
+\n{${\cal P}_A$}{the set of all permutations on a~set~$A$ \[restnota]}
+\n{${\cal P}_{A,M}$}{the set of all permutations on~$A$ satisfying the restrictions~$M$ \[restnota]}
+\n{$N_0(M)$}{the number of permutations satisfying the restrictions~$M$ \[restnota]}
+\n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]}
+\n{$D_n$}{the $n\times n$ matrix with $D[i,i]=0$ for all~$i$ and ones elsewhere else \[hatrank]}
+\n{$\per M$}{the permanent of a~square matrix~$M$}
 }
 
 %--------------------------------------------------------------------------------