Das ist ein Problem aus meinem Lehrbuch. DasCollatz-Vermutung (oder das "3n + 1" -Problem) funktioniert wie folgt (mit einer natürlichen Zahl)n):

while n > 1 do
    if n is even then
        n = n / 2
    else
        n = 3n + 1
    end if
end while

Ich habe ein paar Papiere über die Vermutung überflogen, aber sie gingen mir alle über den Kopf. Ich versuche, ein grundlegendes Verständnis für die Komplexität des Algorithmus zu bekommen. Ist es möglich, eine Ober- oder Untergrenze für die Anzahl der ausgeführten Operationen zu kommentieren (im schlimmsten Fall)?

Das Einzige, woraus ich schließen konnte, ist, dass eine Eingabe im besten Fall die Form n = 2 ^ k haben muss (was zu den wenigsten Operationen führt). Kann man demnach sagen, dass der Worst-Case-Eingang eine Zweierpotenz ist?

Ich habe Probleme damit, eine grobe Ober- oder Untergrenze zu definieren. Für jedennEs scheint, als gäbe es zu viele Wechsel von ungeraden zu geraden (was zu einer Erhöhung um den Faktor 3 oder einer Verringerung um den Faktor 2 führt), um die geringste / meiste Anzahl der durchgeführten Berechnungen zu kommentieren.

Jede Hilfe wird geschätzt.