1
$\begingroup$

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)?

$\endgroup$
2
  • 1
    $\begingroup$ Actual boundary condition(s) of the recurrence is dependent on the actual problem at hand. $\endgroup$
    – Russel
    Commented Apr 6, 2022 at 12:39
  • $\begingroup$ Instead of T(1) = 1, you can let T(1) = c for any c, obviously with different results. You pick whatever is most realistic. Then T(2) = 2c+2, T(3) = 2c+3, T(4) = 4c+8, T(5)=4c+9 etc. etc. $\endgroup$
    – gnasher729
    Commented Apr 7, 2022 at 13:23

1 Answer 1

2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Thank you! I guess $n$ represents the input size and $T(n)$ denotes the (theoretical) running time of the algorithm being analyzed. So, $n$ might range from 0 to any large integer. let $n_0 = n=1,000,000$, what does $n_{1} = \lfloor n_0/2 \rfloor = 500,000$ mean? $\endgroup$
    – JJJohn
    Commented Apr 7, 2022 at 14:41
  • $\begingroup$ I am just defining a sequence of integers: $n_0 = n$, $n_1 = \lfloor n/2 \rfloor$, $n_2 = \bigl\lfloor \lfloor n/2 \rfloor /2 \bigr\rfloor$, and so on. $\endgroup$ Commented Apr 7, 2022 at 14:45
  • $\begingroup$ In the actual application, $n_i$ is the size of the input in recursive calls at depth $i$ of the recursion tree. $\endgroup$ Commented Apr 7, 2022 at 14:45
  • $\begingroup$ Thank you so much. Would you please explain a bit about the relation of $T(n) = T(n_0) + T(n_1) + … + 2^\ell T(1)$ and the result of "unrolling the recurrence" in you answer? In the equation I just gave, $T(n_0)$ denotes the running time of the root of the recursion tree and $T(n)$ denotes overall running time. $\endgroup$
    – JJJohn
    Commented Apr 8, 2022 at 8:05
  • $\begingroup$ I’m afraid you’ll have to work it out on your own. $\endgroup$ Commented Apr 8, 2022 at 8:27

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.