Como resolver a recursão com duas taxas de convergas separadas

Question

Qual é a maneira correta de resolver a seguinte recursão: $ t (n)= t (\ lceil \ frac {n} {2} \ rceil) + t (n-2) $

ou basicamente qualquer recursão que tenha duas partes que convergem de uma taxa diferente.

Estou tentando obter grande $ o $ aproximação, tão apertado quanto possível, mas eu não consegui descobrir com qualquer abordagem "tradicional"./ p >.

Answer 1

Se você fizer as condições iniciais $ t (0)= 0 $ e $ t (1)= 1 $ então você recebe A018819 (até a mudança), que é essencialmente A000123 . Os assintosos são conhecidos por ser $ t (n)= n ^ {\ theta (\ log n)} $ . As referências sob a segunda entrada contêm informações assintóticas mais precisas.

Mais explicitamente, A018819 satisfaz a recorrência $ a (2m + 1)= A (2m)= A (2M-1) + A (m) $ , Com $ a (0)= A (1)= 1 $ . Você pode mostrar indutivamente que $ a (n)= t (n + 1) $ . De fato:

• se $ n= 2m + 1 $ então $$ t (n + 1)= t (2m + 2 )= T (M + 1) + T (2m)= A (m) + A (2m-1)= A (2m)= A (2M + 1)= A (n). $$ < / li >.
• se $ n= 2m $ então $$ t (n + 1)= t (2m + 1)= T (m + 1) + t (2m-1)= A (m) + A (2m-2)= A (M) + A (2m-1)= A (2m)= A (n). $$