되풀이 관계를 풀기

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 

나는 그들을 풀어 낼 생각이 없습니다. 나는 당신을 위해 하나 해결하고

Answer 1

, K 수준에서 그렇게 한
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 합이

01,232,116,765,787,368,251,132 그래서^2 (100분의 29 + (29/100)^2 +... + (29/100)^k)는
이있다 GP

10 [1- (29/100)^로그 (N)]/[1-29/100] 복잡도 N^2