Aufgabe (Mastertheorem)

Hallo!

Aufgabe: Benutzen sie die Master-Methode zur Berechnung der Laufzeit der Suche durch Bisektion mit der Rekurenzgleichung T(n) = T(n/2) + Theta(1).

Nun, in dem Fall ist a = 1, b=2.
Was ist aber f(n)? f(n) = 1 oder f(n) = Theta(1)?

Theta(1) ist eine Funktionsklasse/-menge wie auch immer du sie nennen möchtest. Auf jeden Fall beschreibt Theta(1) eine Ansammlung von Funktionen welche alle asymptotisch die gleiche Laufzeit haben. Bei Theta(1) ist der Repräsentant dieser Klasse die Funktion f(n)=1, du kannst aber auch einen anderen Repräsentanten nehmen, die Klasse ist unabhängig von der Wahl des Repräsentanten.

Nachdem du das weißt wählst du einfach f(n)=1 in deiner Rechnung, alle anderen Funktionen g € Theta(1) haben ja folgende Eigenschaft: a*f <= g <= b*f bzw. a <= g <= b (da f(n)=1) und somit ist auch klar, dass du die Rechnung von f(n)=1 für alle g € Theta(1) durch Modifikation der konstanten Faktoren übertragen kannst (kannst das evt. dazuschreiben braucht man aber nicht, da wie gesagt die Wahl des Repräsentanten für das Ergebnis egal ist - bis auf die konstanten Faktoren im Ergebnis halt, aber die verschwinden dann auch wieder in der Komplexitätsklasse die du rausbekommst).

Danke

Noch eine kleine Frage zur Asymptotik:

Gegeben seien die Fkt. f(n) = sqrt(n) und und g(n) = n^(sin n).

Man soll entscheiden, ob f(n) = O(g(n)) bzw. f(n) = o(g(n)); f(n) = Omega(g(n)) bzw f(n) = klein Omega(g(n)); f(n) = Theta(g(n)).

Da n^(sin n) für n -> unendlich immer zwischen 0 und unendlich schwankt, ist g(n) in dem Fall keine Schranke von f(n). Oder irre ich mich?