Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Section 4.3 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" uses the following recurrence as an example to illustrate the substitution method.
$T(n) = 2T(\lfloor{n/2}\rfloor)+n \tag{4.19}$
That section says
Let us assume, for the sake of argument, that T(1) = 1 is the sole boundary condition of the recurrence.
In reality, does there exist any other boundary condition of the recurrence (4.19)?
Once you specify $T(1)$, the recurrence determines $T(n)$ for all $n \geq 2$. The value of $T(1)$ itself is arbitrary.
Given $n \geq 1$, construct a sequence of integers as follows. The starting point is $n_0 = n$. If $n_i \geq 2$, then $n_{i+1} = \lfloor n_i/2 \rfloor$. The sequence stops once $n_\ell = 1$. You can check that $\ell = \lfloor \log_2 n \rfloor$. Unrolling the recurrence, we have $$ T(n) = n_0 + 2n_1 + 4n_2 + \cdots + 2^{\ell-1}n_{\ell-1} + 2^\ell T(1). $$ Therefore if we define $T_C(n)$ to be the solution to the recurrence with initial condition $T_C(1) = C$, then $$ T(n) = T_0(n) + 2^\ell T(1). $$ Also, $n/2 < 2^\ell \leq n$. Therefore the choice of $T(1)$ only affects the solution by an additive factor of $\Theta(n)$.
