Este é um problema do meu livro didático. oConjectura Collatz (ou o problema "3n + 1") funciona da seguinte forma (dado um número naturaln):

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

Eu passei alguns papéis sobre a conjectura, mas todos eles passaram pela minha cabeça. Eu estou tentando obter uma compreensão básica da complexidade do algoritmo. É possível comentar um limite superior ou inferior para o número de operações realizadas (no pior dos casos)?

A única coisa que eu consegui deduzir é que uma entrada de melhor caso deve ser da forma n = 2 ^ k (que resultará no menor número de ops). A partir disso, é justo dizer que a pior entrada é qualquer poder de dois?

Eu tenho lutado com a tentativa de conceituar um limite superior ou inferior. Para qualquern, parece que há muita mudança de ímpar para par (o que resulta no aumento de um fator de 3 ou redução de um fator de 2) para comentar a quantidade mínima / maior de cálculos realizados.

Qualquer ajuda é apreciada.