Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Is there a general method to solve the recurrence of the form:

$T(n) = T(n-n^c) + T(n^c) + f(n)$

for $c < 1$, or more generally

$T(n) = T(n-g(n)) + T(r(n)) + f(n)$

where $g(n),r(n)$ are some sub-linear functions of $n$.

Update: I have gone through the links the provided below and also sifted through all the recurrence relations in Jeff Erickson's notes. This form of the recurrence is not discussed anywhere. Akkra-Bazi method applies only when the split is fractional. Any poignant reference will be apprieciated.

share|improve this question
Try generating functions. –  saadtaame Feb 25 '13 at 17:00
Does the Akra-Bazzi method apply? It only gives $O(\cdot)$ estimates, but that might be enough. –  vonbrand Feb 25 '13 at 17:02
Since you did not include much of an attempt to solve your problem on your own, we have litte to work with. Let me direct you towards our reference questions which cover problems similar to yours in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. –  Raphael Feb 25 '13 at 17:07
@Raphael, I can't see how the simple recursion problems in reference posts can help the OP? I can't see how this question is easy one and if this is really easy question why we can not see similar comment as yours in too many other simple question, I think this question after some research deserves to be asked in cstheory.stackexchange.com –  user742 Feb 28 '13 at 9:48
Check out Tom Leighton's handouts on "Notes on better master theorems for divide-and-conquer recurrences", they are available on the 'net. Perhaps you can adapt the proof of Akra-Bazzi there to your case. –  vonbrand Mar 7 '13 at 18:48
show 3 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.