Laufzeitanalyse Algorithmus?

Hey, ich brauche Hilfe bei der Laufzeitanalyse, ich hab schon eine Vermutung, aber will es hier noch mal bestätigt haben:

an irgendeinem punkt werden sich beide fälle "gegenseitig aufrufen", wie groß wär t(m,n), (wahrscheinlich O(n+m)??)

Answer 1

[tastyminerals]

Diene Vermutung ist korrekt, die erste case Komplexität ist O(n) , weil die zweite case ist $O(m)+T(m/2,n)$

Die Summe dieser Schritte ergibt eine geometrische Reihe:

$O(m)+O(m/2)+O(m/4)+...=O(m)$ Gesamtkomplexität ist daher O(n + m).