Ich kann versuchen das zu erklären. Sollte etwas nicht so ganz stimmen/ungenau/unverständlich sein - korrigiert mich, bitte.

Master Theorem benutzt man in den Fällen, wo man Rekursion hat bzw. das Algorithmus als Rekursion sich vorstellen kann.
Die Laufzeit wird damit sehr ungenau berechnet, aber für uns reicht das normalerweise.

Erstens in deinem Beispiel:

Ist die Laufzeit [tex]T(n)\approx2=O(1)[/tex]

Aber das hast du wahrscheinlich nicht gemeint.

Eher so was?

Eine gute Erklärung, wie man vorgehen sollte, kann man auf der englischen Wiki-Seite ([urln]http://en.wikipedia.org/wiki/Master_theorem[/urln]) lesen.

Hier für dein (modifiziertes) Beispiel:

Betrachte eine rekursive Version des Algos:

Dort liest man:

n is the size of the problem

Also in unserem Fall [tex]n=1000-100=900[/tex]

a is the number of subproblems in the recursion.

Wir haben nur 1 rekursive Aufruf [tex]a=1[/tex]

n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)

[tex]\frac{n}{b}=\frac{n}{2}\Rightarrow b=2[/tex]

f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

[tex]f(n)\approx2=O(1)[/tex]

Jetzt betrachte [tex]\log_{b}{a}=\log_{2}{1}=0[/tex] und [tex]f(n)=O(1)=O(n^{0})[/tex]
[tex]f(n)=O(n^{0})=\Theta(n^{\log_{b}{a}})[/tex] - 2. Fall

[tex]T(n)=\Theta{(n^{\log_{b}{a}}\cdot\log^{k+1}{n})}[/tex]
[tex]T(n)=\Theta({n^{0}}\log{n})=\Theta{(\log{n})}[/tex]