1
$\begingroup$

We know that a recurrence relation without initial condition(s) might specify more than one solution (if it has any), but if we set some initial condition(s) the solution becomes unique. Now The book CLRS claims for a recurrence like this: $ T(n) = 2T(\lfloor n / 2\rfloor) + n$ or other divide-and-conquer-related recurrences, if we change the initial conditions the solution changes by a constant factor. What is the proof of this? And it's only true for these types of recurrences(divide_and_conquer_related)? Right?

$\endgroup$

1 Answer 1

2
$\begingroup$

Let $T,S$ defined using the same recurrence, but using two different initial conditions: $T(1) = 1$ and $S(1) = 2$. A simple induction shows that $T(n) \leq S(n)$.

On the other hand, consider the recurrence $R(n) = 2R(\lfloor n/2 \rfloor) + n/2$, with initial condition $R(1) = 1$. A simple induction shows that $R(n) = S(n)/2$ and that $R(n) \leq T(n)$, and so $S(n) = 2R(n) \leq 2T(n)$.

$\endgroup$
6
  • $\begingroup$ Thanks. So looks like in the general case the different solutions( with different initial conditions) are $\Theta$ of each other. Is that right? But for what recurrences is this true? For those about the divide-and-conquer approach? $\endgroup$
    – Emad
    Jul 3, 2021 at 17:35
  • $\begingroup$ I mean for recurrence relations like this: $T(n) = aT(n / b) + f(n)$ where $a > 0$ and $b\geq 1$. Of course we can have a linear combination $T(n / b)$s or have $\lfloor n / b \rfloor$ or $\lceil n / b \rceil$ instead of $n / b$. $\endgroup$
    – Emad
    Jul 3, 2021 at 17:42
  • $\begingroup$ It works whenever this kind of proof works. $\endgroup$ Jul 3, 2021 at 17:43
  • $\begingroup$ All right. Thanks. $\endgroup$
    – Emad
    Jul 3, 2021 at 17:44
  • $\begingroup$ It should work for divide and conquer recurrences where the additive term is not wild (say big Theta of some monotone function). $\endgroup$ Jul 3, 2021 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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