Algorithmen[2]#2

[Thomas]

bin mir iwie unsicher wie man hier die oberen schranken beweisen soll. ich habs jetzt mal über vollst. induktion gemacht, hab noch keinen anderen weg gefunden, da beides auch nicht wirklich in die allg. form des master-theorems passt. noch jemand so gemacht oder hab ich was übersehen?

[Ruben]

http://en.wikipedia.org/wiki/Master_the ... ric_form_3
Seltsammerweise ist es auf englisch erweiterter ( ) als auf deutsch. Mit k=1 ist es ganz banal lösbar.

[Cauchy]

Was ist bei der a) die Konstante b? ?

[Blurio]

liegt n² logn in theta von n²?

Falls nicht würd mich das mit k = 1 von rubens interessieren.

[Tankwart]

/e: Hier stand Müll, Theta mit Ohm verwechselt -.-

Hab auch b=sqrt(n)

[Thomas]

ich lass es ma so stehen beschränkt das ganze ja eigentlich nach oben und nach unten

[SLS]

zu a):

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Dies wird nicht mit dem Master-Theorem gelöst, sondern man sollte einfach ausprobieren (durch direktes stufenweises Einsetzen) eine nicht-rekursive formel Formel für T(n) zu finden. Diese sollte man dann durch Induktion beweisen können. Wenn man die geschlossene Formel hat, ist es leicht das Erwünschte zu beweisen

zu b):

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Hier passt es bei mir auch in keinen der drei Fälle des Master-Theorems. Ich bin gerade auf der Suche nach der oberen Schranke...

[Thomas]

gibt wie gesagt die erweiterung mit dem log^k was man im deutschen wikipedia findet wenn man weiter runter scrollt oder im englischen stehts direkt oben
und wenns im teta kalkül liegt liegts ja auch im O-kalkül