1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Replace the free parameters $a,b$ by a maximum over all legal choices of $a,b$. $\endgroup$ – Yuval Filmus May 29 '14 at 15:48
  • $\begingroup$ 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$. $\endgroup$ – user18051 May 29 '14 at 16:59
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for your answer! I don't really know how to analyze this monster now, though, since S' is dependent on T' and vice versa. $\endgroup$ – user18051 May 30 '14 at 7:24
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus May 30 '14 at 15:09
  • $\begingroup$ 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. $\endgroup$ – user18051 May 30 '14 at 17:40
  • $\begingroup$ @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. $\endgroup$ – Yuval Filmus May 31 '14 at 5:15
  • $\begingroup$ Do you happen to know how to solve such a recurrence? I would very much appreciate it if you can give me some directions (or some literature) :) $\endgroup$ – user18051 May 31 '14 at 8:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.