마스터 정리 - 두 번째 케이스 문제

Question

주어진 다음의 재귀 방정식 :

이

T(n) = 5T(n/5)+(5sin^5(5n^5)+5)*n 
T(n) = T(n/4)+2sin^2(n^4) 

내가 쉽게 두 방정식 마스터 정리의 두 번째 경우에 맞는 것을 볼 수 있습니다

,

하지만, 사실로 인해 죄가 있음 원형 함수라면 N 크기가 실제로 0에 가까울 수도 있습니다. 그래서 우리는 항상 마스터 정리와 해결을 정말 가능

인가 .. 두 상수 C1을 위해 그것을 승인합니다 (세타 정의에 의해) (C2)을은 N> N0을 찾을 수있을 것입니다?

감사합니다.

Answer 1

나는 당신이 맞다고 생각합니다. 마스터 정리는 여기에 적용되지 않습니다. 그 이유는 f(n)과 n^(log_b(a)) 사이의 차이가 다항식이어야한다는 것입니다. 귀하의 경우에는

을 (Master Theorem Recurrences: What is exactly polynomial difference? 참조) : ((5sin^5(5n^5)+5)*n)/(n^(log_5(5)))=(5sin^5(5n^5)+5과 마스터 정리는이 경우에 유효하므로, 다항식하지 (2sin^2(n^4))/(n^(log_4(1)))= 2sin^2(n^4).