# Solution to a recurrence changing by a constant factor

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?

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

• 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?
• 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$.