再発関係を解決する

Question

私は今、再会関係を学習しています。そんなこと知ってる;

t(n) = t(n/2) + t(n/5) + n is t(n) = theta n 

t(n) = t(n/2) + t(n/5) + nlogn 
t(n) = t(n/2) + t(n/5) + logn 
t(n) = t(n/2) + t(n/5) + n^2 
t(n) = t(n/2) + t(n/5) + n^1/2 

私はそれらを解決することはできません。私はあなたのための1つ解決しています

Answer 1

、k個のレベルでその1
n/5^k=1 =>n=5^k => k=log(n) having base 5 に/ 5^kが等しくなり、すべての用語の一部をn個のとき

t(n) = t(n/2) + t(n/5) + n^2<br>Using recurrence tree<br> 

      (n) 
    /  \ 
    (n/2)  (n/5)---->   (n/2)^2+(n/5)^2=(29/100)*n^2 
/ \  / \ 
(n/2^2) (n/10) (n/10) (n/5^2)------>(n/4)^2+(n/10)^2+(n/10)^2+(n/25)^2=(29/100)^2*n^2 
|   |    | 
|   |    | 
|   |    | 

これが終わる

Nその合計が

なるよう^ 2（28/100 +（100分の29）^ 2 +···+（100分の29）^ k）は
これはGPあります

10 [1-（100分の29）^ログ（N）]/[1-29/100]複雑さがN^2