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

Question

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

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

n ^ k = 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 ² ).