Master Theorem < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 18:38 Di 06.05.2008 | | Autor: | Wimme |
| Aufgabe | Beschreiben Sie das asymptotische Verhalten folgender Funktionen möglichst genau:
T(n) =3T(n/4)+nlog(n)
T(3n) = 3T(2n)+log(n) |
Hallo!
Bei diesen beiden Aufgaben bin ich mir nicht so ganz sicher, was die Anwendung des Master Theorems angeht.
1) Also ich habe mir gedacht, dass ich nlog(n) einfach nach oben durch [mm] n^{1.5} [/mm] abschätzen kann. Dann hätte ich beim Master Theorem:
a=3,b=4 und p=1.5
damit gilt: [mm] a
2) Hier bin ich doch sehr ob des T(3n) verwirrt. Wie genau gehe ich damit um?
Ich danke für jede Hilfe!
Wimme
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Do 08.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
