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 

が、F（n）は定数-sqrt（N）

私の質問です：

1. は、I（n）はFをとることができる=シータ（sqrt n）、または私が知っているはずのトリックがありますか？

2. また、あなたがそれにいる間、一定のマイナスsqrt（n）を持っているかどうかを説明できるかどうか、つまりマイナス記号は意味がありますか？それは無視することができます。

これは私を夢中にしています！助けてください！ありがとう!!

Answer 1

Master Theoremにはいくつかの前提条件とケース要件があります。それらのいずれかに違反し、定理または事例は適用されない。私が見て分かるように、この場合は、f（n）が正であるという定理要件に違反します。

実際には、2500^2ノードを渡すと、プロセス間通信のオーバーヘッドが負になります。結果は、計算が完了する前に収集され照合されます。

私は、問題の文で間違いがあると思われます。