1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .