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

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.)

• Replace the free parameters $a,b$ by a maximum over all legal choices of $a,b$. – Yuval Filmus May 29 '14 at 15:48
• What do you mean by maximum over all legal choices of $a,b$? For me, that sounds like I should set $a:=x,b:=y$, which would result in $T(x,i,y)=x+y+1+1+1$. – user18051 May 29 '14 at 16:59

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.
• @user18026 Now it's a plain recurrence relation. I agree that it looks difficult to analyze. The circular reference you mention is a red herring since once you substitute the definition $S'$ in the definition of $T$', it disappears. I only wrote it this way to simplify typesetting. – Yuval Filmus May 30 '14 at 15:09
• Can you tell me how to solve such recurrence equations, i.e. bring them into a closed form? After substituting once, I get $$T'(n,2,n) = 2n + \max_{\substack{0 \leq a \leq n\\ 0 \leq b \leq n}} \{\\2(x+y)-(a+b)\\ + max_{\substack{0\leq a_1 \leq x-a\\0\leq b_1 \leq b}}\{...\} + max_{\substack{0\leq a_2 \leq x-a\\0\leq b_2 \leq y-b}}\{...\} + max_{\substack{0\leq a_3 \leq a\\0\leq b_3 \leq y-b}}\{...\} \}$$ But again I end up having trouble analyzing this recurrence, since all the $a_i,b_i's$ are dependent on the input. – user18051 May 30 '14 at 17:40
• @user18051 The $a_i,b_i$ are independent of the input since we're maximizing over them. Regarding how to solve this recurrence, that's a different question. – Yuval Filmus May 31 '14 at 5:15