# Why can $T(x,c)=\theta(x),T(c,y)=\theta(y),T(x,y)=\theta(x+y)+T(x/2,y/2)$ be rewritten as $T(x,y)=c(x+y)+T(x/2,y/2)$

I'm doing a self study on MIT Opencourseware Algorithms course and the first problem set can be found here: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/MIT6_006F11_ps1_sol.pdf.

In Recurence Relations Resolution section this is given $$T(x,c) = \theta(x) \text{ for } c\leq2\\ T(c,y) = \theta(y) \text{ for } c\leq2\\ T(x,y) = \theta(x+y)+T(x/2,y/2)$$

On the first step of this solution is this: $$T(x,y)=c(x,y)+T(x/2,y/2)$$

I have trouble understanding the first step. How did $$\theta(x+y)$$ turn into $$c(x+y)$$?

Things I've done

## 1 Answer

It's incorrect. For example, if $$T(x, y) = x + y + 2^{-x}$$, then it satisfies conditions, but not the first step.

To fix it, we should write $$T(x, y) \leq c\cdot(x _ y) + T(x/2, y/2)$$ and get $$T(x, y) \leq 2c(x, y)$$ (with the same geometric sequence argument). Then we should write $$T(x, y) \geq d\cdot(x + y) + T(x/2, y / 2)$$ (with $$d > 0$$) and get $$T(x, y) \geq d\cdot (x + y)$$. Together it gives us $$T(x, y) = \Theta(x + y)$$.