Special cases.

[saga.git] / notation.tex

diff --git a/notation.tex b/notation.tex
index 9a06dea8b40f795c063dc6dc6a5019625ec1bb2d..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}