Analysis of a recursive algorithm, where running time strongly depends on input

Question

I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where

$T(x, i, y) = \begin{cases} 1 & \textrm{if $(x=0)$ or $(y=0)$ or $(i > n)$} \\ x+y+ T(x-a,\quad i+1, \qquad b)\\ \ \qquad+ T(x-a,\quad i+1,\ y-b)\\ \ \qquad+ T(\quad\ \ \ a,\quad i+1,\ y-b) & \textrm{otherwise} \end{cases}$

where $a \in \{0, ..., x\}, b \in \{0, ..., y\}$, and $a,b$ can be different in each recursion step, dependent on the input.

(Note: $x$ and $y$ represent the sizes of two lists $|L_1|=x, |L_2|=y$, and in each recursion step, each list is split into two, i.e. into lists of size $a$ and $x-a$ (for $L_1$), and $b$ and $y-b$ respectively (for $L_2$).)

How can I analyze such a recurrence equation, i.e. determine $f$ s.t. $T(n, 2, n)\in O(f)$? In particular, I do not know how to deal with $a, b$, especially since they are completely dependent on the input of the algorithm.

(I can solve the recurrence equation for special cases of $a,b$, e.g. $a=\frac{x}{2}, b=\frac{y}{2}$ for all recursion steps, or $a=x, b=0$ for all recursion steps etc., but not in general.)

Answer 1

In order to determine an upper bound on $T(x,i,y)$, consider instead the recurrence $$ T'(x,i,y) = \begin{cases} 1 & \text{if $x = 0$ or $y = 0$ or $i > n$} \\ x + y + \max_{\substack{0 \leq a \leq x\\ 0 \leq b \leq y}} S'(x,i,y,a,b) & \text{otherwise,} \end{cases} $$ where $S'$ is given by $$ S'(x,i,y,a,b) = T'(x-a,i+1,b) + T'(x-a,i+1,y-b) + T'(a,i+1,y-b). $$ If you have more constraints on $a,b$, you should adjust the bounds in the definition of $T'$ accordingly.