Основная теорема - проблема второго случая

Question

Даны следующие рекурсивные уравнения:

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

Я легко вижу, что оба уравнения соответствуют 2-му случаю основной теоремы,

но из-за того, что грех является круговой функцией, кажется, что достаточно большое N может приблизить его к нулю. Таким образом, мы всегда сможем найти N > N0 для двух констант c1,c2 (по определению тета), которые будут отклонять это..

Реально ли это решить с помощью основной теоремы?

Спасибо

Answer 1

Я думаю, что вы правы, основная теорема здесь не применима. Причина этого в том, что разница между f(n) а также n^(log_b(a)) должен быть полиномом. (См. Повторения основной теоремы: что такое полиномиальное различие?)

В твоем случае:((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), что не является полиномом, поэтому основная теорема в этом случае неверна.