2つの別々の収束率で再帰を解決する方法

Question

次の再帰を解決する正しい方法は何ですか。 $ t（n）= t（\ lceil \ frac {n} {2} \ Rceil）+ t（n-2）$

または基本的に異なる速度で収束する2つの部分を有する任意の再帰;

私はBIG $ o $ 近似を可能な限りタイトに入ろうとしていますが、私はどんな「伝統的な」アプローチでそれを理解することができませんでした。

Answer 1

初期条件を取ります $ t（0）= 0 $ と $ t（1）= 1 $ A018819 （Shift）。これは本質的に A000123 。漸近値は $ t（n）= n ^ {\ theta（\ log n）} $ です。 2番目のエントリの下の参照には、より正確な漸近情報が含まれています。

より明示的に、A018819は再発 $ a（2m + 1）= a（2m）= a（2m-1）+ a（m）$ を満たしています。 $ a（0）= a（1）= 1 $ 。 $ a（n）= t（n + 1）$ を誘導的に表示することができます。確かに：

$ n= 2m + 1 $ の場合 $$ t（n + 1）= t（2m + 2 ）= t（m + 1）+ t（2m）= a（m）+ a（2m - 1）= a（2m）= a（2m + 1）= a（n）。$$ < / li>
• $ n= 2M $ の場合、 $$ 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）。$$