So gehe ich vor:

1. Startwert [tex]T(1)[/tex] vergessen
2. [tex]a,\,b[/tex] und [tex]f(n)[/tex] ablesen
3. [tex]n^{\log_{b}{a}}[/tex] ausrechnen
4. Den erhaltenen Wert mit [tex]f(n)[/tex] vergleichen
5.
Stimmt [tex]f(n) = O\left( n^{\log_b \left( a \right) - \epsilon} \right)[/tex]
[tex]\to T(n) = \Theta\left( n^{\log_b a} \right)[/tex] (1. Fall)

Stimmt [tex]f(n) = \Theta\left( n^{\log_b a} \log^{k} n \right)[/tex]
[tex]\to T(n) = \Theta\left( n^{\log_b a} \log^{k+1} n \right)[/tex] (2. Fall)

Stimmt [tex]f(n) = \Omega\left( n^{\log_b a + \epsilon} \right)[/tex] und [tex]a f\left( \frac{n}{b} \right) \le c f(n)[/tex]
[tex]\to T\left(n \right) = \Theta \left(f \left(n \right) \right)[/tex] (3. Fall)

In deinem 1. Beispiel:
[tex]T(1) = 2,\,T(n) = T\left(\frac{n}{2}\right) + \log_2 n[/tex], für [tex]n > 1[/tex]

2. [tex]a=1,\,b=2,\,f(n)=\log_{2}n[/tex]
3. [tex]n^{\log_{2}1}=n^{0}[/tex]
4. [tex]\log_{2}n=\Theta \left( n^{0} \cdot \log \left( n \right) \right)[/tex]
5. 2. Fall: [tex]\to T(n) = \Theta\left( n^0 \log^{0+1} n \right)=\Theta \left( \log n \right)[/tex]

In deinem 2. Beispiel:
2. [tex]a=2,\,b=2,\,f(n)=\ln n[/tex]
3. [tex]n^{\log_{2}2}=n^1[/tex]
4. [tex]\ln n = O(n^{1-\epsilon})[/tex]
5. 1. Fall: [tex]\to R(n) = \Theta \left( n^1 \right)[/tex]

für das zweite Beispiel ist es so denke ich:

ln n = O(n^1-epsilon)

Wenn man ein Epsilon im Intervall [0,1] wählt (wobei 0 und 1 nicht dazugehören) ist ln n auf jeden Fall klein o von n^1-epsilon, und alles, was klein o ist ist auch groß O.

Beim ersten Beispiel versteh ich allerdings nicht, was Du da tust - der zweite Fall des Mastertheorems geht doch eigentlich anders?

Und zwar t(n) = Theta von n hoch log von a zur basis b. Ohne das log von n hoch k.

Edith:
Sehe grad, das ist eine Verallgemeinerung des zweiten Falls.
Allerdings hast Du glaube ich einen kleinen Fehler:
log von n zur basis 2 = Theta von (n^0 * (log n)^1).

Das hieße für die Lösung:

T(n) = Theta von (n^0 * (log n)^2), da es ja für den letzen log hoch k+1 ist.

Allerdings hast Du glaube ich einen kleinen Fehler:log von n zur basis 2 = Theta von (n^0 * (log n)^1).

Stimmt. 1+1=2. Danke.
Bei Logarithmen bei der Laufzeiteinschätzung passe ich auf die Koeffizienten niemals auf, da die Werte immer so klein sind.

Also nochmals:
Bsp. 1:
5. 2. Fall: [tex]\to T(n) = \Theta\left( n^0 \log^{1+1} n \right)=\Theta \left( \log^2 n \right)[/tex]

also den 4. Schritt versteh ich irgendwie bei beien aufgaben überhaupt nicht.. Kannste mal kuz erklären wie du darauf kommst?

[urln]http://en.wikipedia.org/wiki/Master_theorem[/urln]
Es gibt 3 Schemen (3 Fälle), du überprüfst jedes und wählst das passende aus.