When f(n) is negative, how does master theorem apply?

Question

Trying to solve this recursion:

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 

but f(n) is constant -sqrt(n)

My questions:

1. Can I assume f(n) = Theta(sqrt n) or is there some trick I should be knowing?

2. Also, while you are at it, if you could explain if having a constant minus sqrt(n) i.e. is the minus sign have any significance? or it can ignored.

This is driving me crazy! Please help! Thanks!!

Answer 1

The Master Theorem has several prerequisites and case requirements. Violate any one of those, and the theorem or case does not apply. As best I can see, this case violates the theorem requirement that f(n) be positive.

In practical terms, this says that once you pass 2500^2 nodes, the inter-process communication overhead is negative: the results are collected and collated before their computation is completed.

I strongly suspect an error in the problem statement.