1

$T(1) = a$ and $T(2) = b$ - terminating base cases. In general, $T(n) = min_{1\leq k \leq n-1} (T(k) + T(n-k)) + 2$.

For the typical non-homogeneous linear recurrence, we need to solve for the associated homogeneous solution. But this recurrence does not have non-zero constant coefficients for $T(n-1)$ and/or $T(n-2)$.

And, to get rid of the minimum, we have to make assumptions, and the relation, which is broad enough to cover the possibility of a divide-and-conquer solution, might end up with a specific solution instead of a general one.

How do I proceed safely? What should be my line of approach for this problem?

0 Answers0