Este es un problema de mi libro de texto. losConjetura de collatz (o el problema "3n + 1") funciona de la siguiente manera (dado un número naturaln):

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

Hojeé algunos artículos sobre la conjetura, pero todos pasaron por alto mi cabeza. Estoy tratando de obtener una comprensión básica de la complejidad del algoritmo. ¿Es posible comentar sobre un límite superior o inferior para el número de operaciones realizadas (en el peor de los casos)?

Lo único que he podido deducir es que una entrada en el mejor de los casos debe ser de la forma n = 2 ^ k (que dará como resultado la menor cantidad de operaciones). A partir de esto, ¿es justo decir que la entrada en el peor de los casos es la falta de poder de dos?

He estado luchando para intentar conceptualizar un límite superior o inferior aproximado. Para cualquiern, parece como si hubiera un cambio excesivo de impar a par (lo que resulta en un aumento de un factor de 3 o una reducción de un factor de 2) para comentar sobre la cantidad mínima / más alta de cálculos realizados.

Cualquier ayuda es apreciada.