Ein Algorithmus teilt ein Problem der Größe n in zwei Teil Probleme jeweils der der Größe n − 1 auf und löst diese rekursiv. Das Zusammenfügen passiert in Θ(1). In welche Komplexität liegt dieser Algorithmus jetzt?
Beim Mergesort ist es beispielsweise ja so, dass wir die Eingabe n in triviale Probleme der Größe 1 zerlegen (in log2(n) Schritten - Ebenen) und diese dann geordnet zusammenfügen mit dem Aufwand n. Bei unserem gegebenen Beispiel hat man n Ebenen und und das Zusammenfassen ist Θ(1). Habe ich also die Laufzeit Θ(n)?