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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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