I have a recurrence relation that goes something like this:



Under the conditions:

$n_1+n_2=n$ $\quad$ & $\quad$ $n_1,n_2 \le 2n/3$

How does we solve such recurrence relations in general?

Worst case complexity might be sufficient for this relation. I was trying to apply Master's theorem but the relation isn't in a format for applying such a technique.

Any insight would be of great help. Thanks.

  • 1
    $\begingroup$ Using the Akra-Bazzi Method, and my guess would be to use $n_1 = n_2 = n/2$ and $n_1 = 2n/3$ along with $n_2 = n/3$ and just pick the bigger complexity. $\endgroup$ – Mohamad Ali Baydoun Dec 3 '17 at 16:57
  • $\begingroup$ That is one my questions. How do we pick n1 & n2 such that complexity is maximum? There are infinitely many values for n1 & n2 which satisfy the constraints n1+n2=n & (n1, n2) <= 2n/3 $\endgroup$ – Adithya Upadhya Dec 3 '17 at 17:02
  • $\begingroup$ I will look int Akra-Bazzi method. Seems very complex... $\endgroup$ – Adithya Upadhya Dec 3 '17 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.