アルゴリズム漸化

Question

はどのように解決し、次の漸化関係しますので、パターンが浮上している

O(1) is lower or equal than a constant c. 

ので

T(n) <= 2T(n-2) + c 
T(n) <= 4T(n-4) + 2c 
T(n) <= 8T(n-6) + 3c 
      . 
      . 
      . 

：

T(n) = 2T(n-2)+O(1) 

私がこれまでにしようとしていることです。一般用語は：

です

しかし、私はthere.Anyアドバイスから継続する方法を知りません。 k=n/2については

Answer 1

kのためのあなたの一般化が真^{であると仮定すると、[1]}

T(n) <= 2^k*T(n-2k) + kc 

あなたが得る：

O(sqrt(2^n))

に正式な証明が誘導で行うことができますされ

T(n) <= 2^n/2 * T(0) + n/2 * c = 2^(n/2) + n/2*c 

を、帰納仮説：

T(n) <= 2^(n/2) + c*n 

ステップの：

T(n) = 2T(n-2) + c = (induction hypothesis) 
T(n) = 2* 2^((n-2)/2) + (n-2)*c + c 
T(n) = 2^ (n/2 - 2/2 + 1) + (n-1)*c 
And indeed: 
T(n) = 2^(n/2) + (n-1)*c <= 2^(n/2) + c*n 

---

（1）それは、一定のループで乗算されているという事実を無視し、ありません。