0
$\begingroup$

Pages 90-91 of 'Introduction to Algorithms' (4th ed.) show how the substitution method can be used for determining the upper bound on the recurrence:

$$T(n) = 2T(\lfloor n/2 \rfloor) + \Theta(n) \tag{4.11}$$

We guess that $T(n) = O(n \lg n)$ and try to prove $T(n) \leq cn \lg n$ by induction.

I can follow the proof for the inductive case, but need some help understanding the proof for the base cases of the induction (I've highlighted the part I'm unsure about in bold):

We’ve shown that the inductive hypothesis holds for the inductive case, but we also need to prove that the inductive hypothesis holds for the base cases of the induction, that is, that $T(n) \leq cn \lg n$ when $n0 ≤ n < 2n_0$. As long as $n0 > 1$ (a new constraint on $n_0$), we have $\lg n > 0$, which implies that $n \lg n > 0$. So let’s pick $n_0 = 2$. Since the base case of recurrence (4.11) is not stated explicitly, by our convention, $T(n)$ is algorithmic, which means that $T(2)$ and $T(3)$ are constant (as they should be if they describe the worst-case running time of any real program on inputs of size 2 or 3). Picking $c = \max[T(2), T(3)]$ yields $T(2) ≤ c < (2 \lg 2)c$ and $T(3) ≤ c < (3 \lg 3)c$, establishing the inductive hypothesis for the base cases. Thus, we have $T(n) ≤ cn \lg n$ for all $n ≥ 2$, which implies that the solution to recurrence (4.11) is $T(n) = O(n \lg n)$.

Questions:

  1. I don't understand the part of the proof in bold: "Since the base case of recurrence (4.11) is not stated explicitly, by our convention, $T(n)$ is algorithmic, which means that $T(2)$ and $T(3)$ are constant". The convention that the authors are referring to is stated on page 78:

    We adopt the following convention:

    Whenever a recurrence is stated without an explicit base case, we assume that the recurrence is algorithmic.

    That means you’re free to pick any sufficiently large threshold constant $n_0$ for the range of base cases where $T(n) = Θ(1)$.

    So by assuming that $T(2)$ and $T(3)$ are constant, we are treating them as base cases of the recurrence, is this correct? If so, how can we simultaneously consider them to be base cases of the induction? The base cases of the induction are input sizes in the range $n_0 ≤ n < 2n_0$, but the base cases of the recurrence are input sizes $n < n_0$ (not sure of this). So, how can $T(2)$ and $T(3)$ be in both sets?

  2. The authors conclude the proof by saying that "Thus, we have $T(n) ≤ cn \lg n$ for all $n ≥ 2$...". They mention the constraint on $n$, but not the constraint on $c$, why is this? Shouldn't they say something like "Thus, we have $T(n) ≤ cn \lg n$ for all $n ≥ 2$ and $c \geq \max[T(2), T(3)]$..." instead?

$\endgroup$

1 Answer 1

0
$\begingroup$
  1. The confusion comes from the fact that the $n_0$ doesn't need to have the same value in both definitions. In the inductive proof, it's mentioned that $n_0$ is taken to be $2$, while the base cases of the recurrence are using $n_0 = 4$ so that $T(2)$ and $T(3)$ are constants.

  2. The definition of $f(n) = O(g(n))$ is "There exist constants $0 < c, n_0$ such that for every $n > n_0$, $f(n) < cg(n)$". To prove that $f(n) = O(g(n))$, it's enough to find specific values for this. In the proof, they take $n_0 = 1$ and $c = \max[T(2),T(3)]$, so their conclusion shows that $T(n) = O(n\lg n)$.

$\endgroup$
2
  • $\begingroup$ Thank you. Just to clarify, why is it safe to assume that $n = 2$ and $n = 3$ are base cases of the recurrence without any knowledge of the algorithm being analysed? If we're talking about merge sort, then a problem size of $n = 3$ does result in further recursion, so why is it acceptable to treat it as a base case? Is it just that $n = 2$ and $n = 3$ are sort of "de facto" base cases in the sense that they are so small that they can be expected to take constant time in the real world? $\endgroup$
    – user51462
    Jun 10, 2023 at 23:29
  • $\begingroup$ @user51462 For any fixed value of $n$, $T(n)$ is a constant. In asymptotic analysis we talk about the behavior of the function as $n$ changes. $\endgroup$ Jun 11, 2023 at 3:49

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.