\documentclass[a4paper,10pt]{scrartcl}
\setlength{\topmargin}{-2cm}
\setlength{\oddsidemargin}{-1.5cm}
\setlength{\evensidemargin}{-1.5cm}
\setlength{\textwidth}{18cm}
\setlength{\textheight}{24cm}

\usepackage[active]{srcltx}
\usepackage[german]{babel}
\usepackage[utf8]{inputenc}
%\usepackage[pdftex,a4paper,colorlinks=true,linkcolor=black]{hyperref}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{graphicx}
%\usepackage{trfsigns}
\usepackage[usenames]{color}
\usepackage{listings}

% Shortcuts für Matrizen, '&' und '\\' gelten wie gewohnt
\newcommand{\mtrx}[1]{\begin{matrix}#1\end{matrix}} % ( normal Matrix )
\newcommand{\smtrx}[1]{\begin{smallmatrix}#1\end{smallmatrix}} % ( small Matrix )
\newcommand{\pmtrx}[1]{\begin{pmatrix}#1\end{pmatrix}}	% ( (...) )
\newcommand{\bmtrx}[1]{\begin{bmatrix}#1\end{bmatrix}}	% ( [...] )
\newcommand{\Bmtrx}[1]{\begin{Bmatrix}#1\end{Bmatrix}}	% ( {...} )
\newcommand{\e}{\text{e}}
\newcommand{\im}{\text{i}}
\newcommand{\mpp}[2][160pt]{\begin{minipage}{#1}\vspace{3pt}#2\vspace{3pt}\end{minipage}}
\newcommand{\mpd}[1]{\mpp[80pt]{#1}}
\newcommand{\mps}[1]{\mpp[110pt]{#1}}

\begin{document}

\begin{tabular}{l||l|l|l}
	& \textbf{Erster Fall} & \textbf{Zweiter Fall} & \textbf{Dritter Fall} \\
	\hline
	\hline
	\mpd{Allgemein gilt:}
	& \mps{$f(n) \in \mathcal O(n^{\log_b a} - \varepsilon)$ für ein $\varepsilon > 0$}
	& \mps{$f(n) \in \Theta(n^{\log_b a})$}
	& \mpp{$f(n) \in \Omega(n^{\log_b a + \varepsilon})$ für ein $\varepsilon \ge 0$, und ein $c$ mit $0 < c < 1$ und hin\-rei\-chend große $n$ gilt: $af(\frac{n}{b}) \leq cf(n)$} \\
	\hline
	\mpd{Dann folgt:}
	& \mps{$T(n) \in \Theta(n^{\log_b a})$}
	& \mps{$T(n) \in \Theta(n^{\log_b a} \log(n))$}
	& \mpp{$T(n) \in \Theta(f(n))$} \\
	\hline
	\mpd{Beispiel:}
	& \mps{$T(n) = 8T(\frac{n}{2}) + 1000n^2$}
	& \mps{$T(n) = 2T(\frac{n}{2}) + 10n$}
	& \mpp{$T(n) = 2T(\frac{n}{2}) + n^2$} \\
	\hline
	\mpd{Aus der Formel:}
	& \mps{$a = 8$, $b = 2$,\\ $f(n)=1000n^2$,\\ $\log_b a = \log_2 8 = 3$}
	& \mps{$a = 2$, $b = 2$,\\ $f(n)=10n$,\\$\log_b a = \log_2 2 = 1$}
	& \mpp{$a = 2$, $b = 2$,\\ $f(n)=n^2$,\\$\log_b a = \log_2 2 = 1$} \\
	\hline
	\mpd{1. Bedingung:}
	& \mps{$f(n) \in \mathcal O(n^{\log_b a} - \varepsilon)$ für ein $\varepsilon > 0$}
	& \mps{$f(n) \in \Theta(n^{\log_b a})$}
	& \mpp{$f(n) \in \Omega(n^{\log_b a + \varepsilon})$ für ein $\varepsilon > 1$} \\
	\hline
	\mpd{Werte einsetzen:}
	& \mps{$1000n^2 \in \mathcal O(n^{3-\varepsilon})$}
	& \mps{$10n \in \Theta(n^1)$}
	& \mpp{$n^2 \in \Omega(n^{1 + \varepsilon})$} \\
	\hline
	\mpd{Wähle $\varepsilon > 0$:}
	& \mps{$1000n^2 \in \mathcal O(n^2) \; \surd$}
	& \mps{$10n \in \Theta(n) \; \surd$}
	& \mpp{$n^2 \in \Omega(n^2)$ mit $\varepsilon = 1 \; \surd$} \\
	\hline
	\mpd{2. Bedingung:\\(nur im 3. Fall)}
	& & & \mpp{$af(\frac{n}{b}) \leq cf(n)$,\\
	$\Rightarrow 2(\frac{n}{b})^2 \leq cn^2 \Leftrightarrow \frac{1}{2}n^2 \leq cn^2$.\\
	Wähle $c=\frac{1}{2}: \forall n\ge1 \colon \frac{1}{2}n^2 \leq \frac{1}{2}n^2 \; \surd$} \\
	\hline
	\mpd{Ist die Bedingung erfüllt:}
	& \mps{$T(n) \in \Theta(n^{\log_b a})$}
	& \mps{$T(n) \in \Theta(n^{\log_b a} log(n))$}
	& \mpp{$T(n) \in \Theta(f(n))$} \\
	\hline
	\mpd{Für die Laufzeitfunktion gilt:}
	& \mps{$T(n) \in \Theta(n^3)$}
	& \mps{$T(n) \in \Theta(n \log n)$}
	& \mpp{$T(n) \in \Theta(n^2)$}
\end{tabular}


\end{document}