Master-Theorem < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 17:39 Mi 17.07.2013 | | Autor: | bandchef |
| Aufgabe | Beweisen Sie folgende Aussage mit dem Master-Theorem:
Sei $T(1) = 1, T(n) = [mm] 3T\left(\frac{n}{4}\right) [/mm] + n log(n) [mm] \forall [/mm] n>1$, dann $T(n) = [mm] \Theta(n [/mm] log(n))$ |
Hi Leute!
Ich hab hier eine Frage zum Master-Theorem:
Aus der obigen Gleichung kann man für den ersten Fall $f(n) = [mm] O\left(n^{log_b(a)-\epsilon}\right)$ [/mm] des Master-Theorems diese Gleichung ablesen: [mm] $n\cdot [/mm] log(n) = [mm] O\left(n^{log_4(3)-\epsilon}\right)$.
[/mm]
Aber: Wie erkenne ich denn nun, ob [mm] $O\left(n^{log_4(3)-\epsilon}\right)$ [/mm] nun wirklich eine obere Schranke von [mm] $n\cdot [/mm] log(n)$ ist? Wie geht das?
Muss man da nun auf beiden Seiten der Gleichung Testwerte für n einsetzen (bspw. 5) und dann schaun, ob die rechte Seite der Gleichung wirklich eine obere Schranke wird?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:40 Mi 17.07.2013 | | Autor: | Diophant |
Hallo bandchef,
das hier ist zum wiederholten Male ein Crossposting. Da man dich jetzt schon öfters aufgefordert hat, dies zu unterlassen, muss man das schon als sehr dreist bewerten.
Die andere Frage ist unter dem gleichen Nickname und mit gleichem Titel auf matheplanet.de zu finden. Da ich gerade vom Handy aus schreibe, sehe ich aber jetzt nicht mehr ein, einen Handstand zu machen um das zu verlinken.
Ich würde vorschlagen, du gibst jetzt vor dem Einstellen neuer Fragen hier mal eine Erklärung ab, dass du in Zukunft gewillt bist, dich an unsere Forenregeln zu halten.
Gruß, Diophant
|
|
|
|
