diff --git a/is/ub8/is8.pdf b/is/ub8/is8.pdf index 78a66e0..672e213 100644 --- a/is/ub8/is8.pdf +++ b/is/ub8/is8.pdf Binary files differ diff --git a/is/ub8/is8.tex b/is/ub8/is8.tex index 907ed54..7fb53d0 100644 --- a/is/ub8/is8.tex +++ b/is/ub8/is8.tex @@ -139,10 +139,28 @@ \item worst case:\\ All nodes are dependent of each other, so it has to check all possible subsets (the powerset) for all pairs of nodes: $$\frac{p\cdot (p-1)}{2}\cdot 2^{p-2}\in\mathcal{O}(2^p)$$ + \begin{tikzpicture}[auto, node distance=2cm] + \node[circle, draw] (A) {A}; + \node[circle, draw] (B) [right of=A] {B}; + \node[circle, draw] (C) [below of=A] {C}; + \node[circle, draw] (D) [below of=B] {D}; + + \draw (A) -- (B); + \draw (A) -- (D); + \draw (B) -- (D); + \draw (B) -- (C); + \draw (C) -- (D); + \draw (C) -- (A); + \end{tikzpicture}\\ \item best case:\\ first test shows independence, so we need only one test per pair: $$\frac{p\cdot (p-1)}{2}\cdot 1\in\mathcal{O}(p^2)$$ + \begin{tikzpicture}[auto, node distance=2cm] + \node[circle, draw] (A) {A}; + \node[circle, draw] (B) [right of=A] {B}; + \node[circle, draw] (C) [below of=A] {C}; + \node[circle, draw] (D) [below of=B] {D}; + \end{tikzpicture}\\ \end{itemize} - %TODO Graphs \end{document}