0 Daumen
158 Aufrufe

ich habe eine Aufgabe, bei der ich das Master-Theorem anwenden soll. Nach langen hin und her und vielen Fragezeichen in meinem Kopf, bin ich auf folgende Lösung gekommen und würde gerne wissen, ob das so richtig ist:


a) T(n) = 9 T(n/3) + n => T(n) = Θ (n^2)

b) T(n) = T(2n/3) + 1 => T(n) = Θ (log(n))

c) T(n) = 9 T(n/5) + n log^14 (n) => T(n) = Θ (n^{1,365} log(n)) (hier habe ich Logarithmus von 9 zur Basis 5 gerundet)

d) T(n) = 2 T(n/2) + n log(n) => T(n) = Θ (n log (n))

von

1 Antwort

0 Daumen

Deine Ergebnisse passen. Ich würde an Deiner Stelle allerdings noch \(\log_2\) statt \(\log\) schreiben.

Zur Kontrolle: https://books.google.de/books?id=6eIPgTo8AaIC&pg=PA25#v=onepage&q&f=false

von 8,3 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
0 Daumen
1 Antwort

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...