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
- I watched the 1 and 2 lecture videos here: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/
- I looked at lecture notes 1 and 2 here: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-notes/
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)$.