Не является положительным, если следующее решение является случаем 3 основной теоремы

Question

Поэтому мне было интересно, будет ли считаться, что следующее повторение подпадает под случай 3 основной теоремы: T(n)=4T(n/2) + 10000 - 5000sin(n).

Поэтому я обозначил свой ответ следующим образом:A = 4, B = 2, F (N) = 10000 - 5000sin (n)

п ^ к = п ^2

Таким образом, сравнивая F(n) с n^k, мы видим, что f (n) растет быстрее, чем n^k, подразумевая, что это случай 3 основной теоремы. Это правильно?

Answer 1

Поскольку -1 ≤ sin(n) ≤ 1, 5000 ≤ f(n) ≤ 15000, что равно O(1), поскольку оно никогда не увеличивается с размером входного сигнала.

Это третий случай, потому что f (n) постоянное время (O(1) == n⁰), что асимптотически меньше, чем n^log₂4. Итак, по основной теореме ваше рекуррентное соотношение T (n) = Θ (n²).