0 Daumen
1,2k Aufrufe

Hallo :)

Ich habe folgende Aufgabe:

Ich soll die Laufzeit eines Algorithmus bestimmen (O-Notation) und das mithilfe des Master-Theorems.

Algorithmus:

fun .jpg



Mein Problem:

Normalerweise weiß ich wie man den Master-Theorem anwendet, aber nur wenn mir schon die Funktionen gegeben sind also als beispiel T(n)= T(n/2)+3n mit T(1)=3 und das wäre  O(n).

Wenn mir jedoch ein Algorithmus gegeben ist, weiß ich nicht, wie ich hier sowas wie  "T(n)= T(n/2)+3 mit T(1)=3" schreiben oder direkt die Laufzeit in O-Notation bestimmen kann.


Kann mir jemand helfen ? Danke im Voraus :)

Avatar von

Bei der Aufgabe stand auch, dass wir annehmen sollen, dass jede Addition und Multiplikation jeweils eine Zeiteinheit benötigt und Zuweisungen momentan sind.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community