Aufgabe 1

Analog zum Beispiel in der Vorlesung, wird die Bedingung der while() Schleife nicht als Vergleich gezählt.

Wir gehen davon aus, dass die Implementation der Programmiersprache nicht intelligent genug ist, um bei einem nicht exklusiven Oder, die rechte Bedingung nicht auszuführen, wenn die linke bereits WAHR ist.

  1. $W(n) = 2((n)/2+ n mod 2)$

  2. $B(n) = 2$

  3. $ Pr{K in E} = 0.3 $
    $ A_{K !in E}(n) = W(n) = 3((n)/2+ n mod 2)$
    $ Pr{K !in E} = 0.7 $
    $ {: (A_{K in E}(n),=,sum_{i=0}^{n-1} 2/n*(i+2)), (,=, 2/n*(n(n+1))/2), (,=,(n+1)/2) :} $

    $A(n) = Pr{K in E} * A_{K in E}(n) + Pr{K !in E} * A_{K !in E}(n)$
    $ => A(n) = 0.3 * (n+1)/2 + 0.7 * 3 * ((n)/2 + n mod 2) $

Aufgabe 2

  1. $ g in Theta(f) text(gdw.) g in O(f) ^^^ g in Omega(f) $
    $ g in O(n) text(gdw) text( limsup)_{n->∞} g(n)/f(n) = c >= 0 ^^^ c != ∞$
    $ => c = text(limsup)_{n->∞} (347n^3+44n^2+745)/n^3 $
    $ <=> c = 347 ^^^ c >= 0 ^^^ c != ∞ $


    $ g in Omega(f^3) text(gdw liminf)_{n->∞} g(n)/f(n) > 0 $
    $ => c = text(liminf)_{n->∞} (347n^3+44n^2+745)/n^3 $
    $ <=> c = 347 ^^^ c > 0 $


    $ g(n) in Theta(n3) $
    $square $

  2. $ g in Theta(f) text(gdw.) g in O(f) ^^^ g in Omega(f) $
    $ g in O(n) text(gdw) text( limsup)_{n->∞} g(n)/f(n) = c >= 0 ^^^ c != ∞$
    $ => c = text(limisup)_{n->∞} 2^{n+1}/2^n $ $ <=> c = 2 ^^^ c >= 0 c != ∞ $


    $ g in Omega(f^3) text(gdw liminf)_{n->∞} g(n)/f(n) > 0 $
    $ => c = text(liminf)_{n->∞} 2^{n+1}/2^n $
    $ <=> c = 2 ^^^ c > 0 $


    $ 2^{n+1} in Theta(2^n) $ $square $

  3. $ g in O(n) text(gdw) text( limsup)_{n->∞} g(n)/f(n) = c >= 0 ^^^ c != ∞$
    $ => c = text(limisup)_{n->∞} log(n)/sqrt(n) $
    $ <=> c = 0 ^^^ c >= 0 ^^^ c != ∞ $


    $ log(n) in O(sqrt(n)) $ $square $

  4. Angenommen $ f(n) = -1 ^^^ g(n) = 0 $ dann folgt daraus
    $ c = text(liminf)_{n->∞} (text(max)(-1,0))/(-1+0) $
    $ <=> c = 0 $
    $ => c !in Omega $ da $ c = 0 $


    $ => max(f(n), g(n)) !in Theta(f(n)+g(n)) $ $square $

  5. Angenommen $ g(n) = 23 ^^^ f(n) = n^{e+n} $ dann folgt daraus
    $ c = text(liminf)_{n->∞} (23+n^{e+n})/(23) $
    $ <=> c = ∞ $
    $ => c !in O(g(f(n))) square$

Aufgabe 3

  1. $ o(f') text( gdw. ) AA n >= n_0 : 0 <= q'(n) < c * f'(n) $
    $ o(f'') text( gdw. ) AA n >= n_0 : 0 <= c * f''(n) < q''(n)$
    $ f''(n) = f'(n) $
    $ => 0 <= q'(n) < c*f'(n) < q''(n) $
    $ => q'(n) != q''(n) $
    $ => o(f(n) nn omega(f(n)) = O/$
    $square $