Recurrence equation with Θ

98 Views Asked by At

I was studying a book and I came through an exercise which I can't solve. The problem is I do not fully understand the question.

The answer must be the solution of the recurrence relation. As it is from an Algorithm book, I suppose the answer must be in the form of Big-Theta.

($\Theta$ is big theta)

$T(x,c) = \Theta(x), \mbox{ for }c \leq 2 $

$T(x,y) = \Theta(x) + S(x, \frac{y}{2})$

$S(c,y) = \Theta(y),\mbox{ for }c \leq 2 $

$S(x,y) = \Theta(y) + T(\frac{x}{2}, y)$

I do not want the answer itself. Any explanation which leads me to the answer is appreciated.

1

There are 1 best solutions below

2
On

Here is a similar example in one variable:
$T(x)=T\left(\dfrac{x}{2}\right)+k$
Put $x={2^n}$

$T(2^n)=T\left({2^{n-1}}\right)+k$

$\therefore T(x)=k\log_2(x)+C$

Here is a Link for Recurrence Equations with >1 variable.