Ecuación de recurrencia con Θ

Question

Estaba estudiando un libro y me encontré con un ejercicio que no puedo resolver. El problema es que no entiendo bien la pregunta.

La respuesta debe ser la solución de la relación de recurrencia. Como es de un libro de Algoritmos, supongo que la respuesta debe ser en forma de Big-Theta.

( $\Theta$ es una gran 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)$

No quiero la respuesta en sí. Se agradece cualquier explicación que me lleve a la respuesta.

Answer 1

Este es un ejemplo similar en una variable :
$T(x)=T\left(\dfrac{x}{2}\right)+k$
Poner $x={2^n}$

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

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

Aquí hay una Enlace para Ecuaciones de Recurrencia con >1 variable.