Master theorem - second case issue

Question

Given the following recursive equations:

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

I can easily see that both equations fit the 2nd case of the master theorem,

but due to the fact that sin is a circular function, it seems that a large enough N might bring it really close to zero. So, we will always be able to find an N > N0 for two constants c1,c2 (By theta definition) which will disapprove it..

Is it really possible solving it with the master theorem?

thanks

Answer 1

I think you're right, the Master Theorem does not apply here. The reason for this is that the difference between f(n) and n^(log_b(a)) has to be polynomial. (See Master Theorem Recurrences: What is exactly polynomial difference?)

In your case: ((5sin^5(5n^5)+5)*n)/(n^(log_5(5)))=(5sin^5(5n^5)+5and (2sin^2(n^4))/(n^(log_4(1)))= 2sin^2(n^4), which is not polynomial, so Master Theorem is invalid in this case.