$ T（n）= T（n/2）+ T（n/4）+ O（m）のような漸化関係を解く方法$

Question

私はこの再帰の厳しい境界を取得したい2つの変数mとn。

Answer 1

私の前の回答hereから、我々はT(n)ため二項の和式を導出することができます

Cをn = Cが停止条件であるようなものですT(n)。

---

特定の例では、定数はc1 = 1, c2 = 1, a = 2, b = 4, f(n) = O(m)です。 O(m)はnに依存しないので、単にfの語句をそれに置き換えることができます。

我々は内側の合計をどのように評価しますか？整数べき乗のための二項展開思い出し：a = b = 1の設定

を我々が得る：

したがって

：