Когда f (n) отрицательно, как применяется мастер-теорема?

Question

Попытка решить эту рекурсию:

T(n) = 4T(n/2) + 2500 - sqrt(n) 
here a = 4, b=2 but my f(n) = 2500 -sqrt(n) 
n^ logb(a) = n^log2 (4) = n ^2 

но е (п) постоянна -sqrt (п)

Мои вопросы:

1. Могу ли я предполагать п (п) = Theta (sqrt n) или есть какой-то трюк, который я должен знать?

2. Кроме того, пока вы на нем, если бы вы могли объяснить, имеет ли постоянный минус sqrt (n), то есть знак минус, какое-либо значение? или он может быть проигнорирован.

Это сводит меня с ума! Пожалуйста помоги! Благодаря!!

Answer 1

Master Theorem имеет несколько предварительных условий и требований к корпусу. Нарушить любой из них, и теорема или случай не применяются. Насколько я вижу, этот случай нарушает требование теоремы о том, что f (n) положительно.

В практическом плане это говорит о том, что после того, как вы передаете 2500^2 узлов, служебные данные межпроцессного взаимодействия отрицательны: результаты собираются и сопоставляются до завершения их вычисления.

Я сильно подозреваю ошибку в описании проблемы.