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

$\endgroup$
2
  • 1
    $\begingroup$ Replace the free parameters $a,b$ by a maximum over all legal choices of $a,b$. $\endgroup$ May 29, 2014 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, 2014 at 16:59

1 Answer 1

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.

$\endgroup$
5
  • $\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, 2014 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$ May 30, 2014 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, 2014 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$ May 31, 2014 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, 2014 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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