Binomialkoeffizient und ONotation

24.05.2013, 19:09

helpMePls

Binomialkoeffizient und ONotation

Meine Frage:
Hi,

also gegeben sei folgender Binomialkoeffizient

$\begin{eqnarray*} \begin{pmatrix} 2n \\ 2 \end{pmatrix} \end{eqnarray*}$

Dieser soll mit der O-Notation abgeschätzt werden.

Meine Ideen:
Als erstes hab ich nun den Binomialkoeffizient mit der Formel aus dem Tafelwerk:

$\begin{eqnarray*} \begin{pmatrix} n \\ k \end{pmatrix}=\frac{n(n-1)*...*(n-k+1)}{k!} \end{eqnarray*}$

umgeformt zu:
$\begin{eqnarray*} \begin{pmatrix} 2n \\ 2 \end{pmatrix}=\frac{2n(2n-1)*...*(2n-2+1)}{2!} \end{eqnarray*}$

nur wie schließ ich nun davon auf $\begin{eqnarray*} \leq 2n^2 \in O(n^2) \end{eqnarray*}$

24.05.2013, 20:01

HAL 9000

Auf diesen Beitrag antworten »

Die ... im Zähler von $\begin{eqnarray*} \binom{2n}{2} \end{eqnarray*}$ sind pure Übertreibung von dir:

Tatsächlich stehen dort nur zwei Faktoren, nämlich $\begin{eqnarray*} (2n)\cdot (2n-1) \end{eqnarray*}$ . Big Laugh

26.05.2013, 14:58

helpMePls

Auf diesen Beitrag antworten »

hehe joa hab ich auch bemerkt^^ ... zur Vollständigkeit:

$\begin{eqnarray*} \frac{2n(2n-1)}{2} =\frac{4n^2-2n}{2}\leq \frac{4n^2-2n^2}{2}=\frac{2n^2}{2} =\frac{1}{2} *2n^2=n^2 \in O(n^2) \end{eqnarray*}$

26.05.2013, 16:29

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von helpMePls
$\begin{eqnarray*} \frac{2n(2n-1)}{2} =\frac{4n^2-2n}{2}~{\color{red} \leq}~\frac{4n^2-2n^2}{2}=\frac{2n^2}{2} =\frac{1}{2} *2n^2=n^2 \in O(n^2) \end{eqnarray*}$

Abschätzung $\begin{eqnarray*} {\color{red} \leq} \end{eqnarray*}$ ist falsch, dort müsste $\begin{eqnarray*} \geq \end{eqnarray*}$ stehen, was allerdings hinsichtlich des Ziels sinnlos wäre. Warum nicht einfach so:

$\begin{eqnarray*} \frac{2n(2n-1)}{2} =\frac{4n^2-2n}{2} \leq \frac{4n^2}{2} = 2n^2 \in O(n^2) \end{eqnarray*}$ .

26.05.2013, 16:38

helpMePls

Auf diesen Beitrag antworten »

Achso verdammt stimmt, danke smile

Neue Frage »

Antworten »

Binomialkoeffizient und ONotation

Verwandte Themen