For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$

Question

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that few things probably mismatch with respect to the range of $n$, the input size for which $T(n)$ is assumes $O(1)$ and $cn$ in the substitution method.

The details of the text are as follows:

---

We can now develop a recurrence for the worst-case running time $T(n)$ of the algorithm SELECT. Steps 1, 2, and 4 take $O(n)$ time. (Step 2 consists of $O(n)$ calls of insertion sort on sets of size $O(1)$ Step 3 takes time $T(\lceil n/5 \rceil)$, and step 5 takes time at most $T(7n/10+ 6)$, assuming that T is monotonically increasing. We make the assumption, which seems unmotivated at first, that any input of fewer than $140$ elements requires $O(1)$ time; the origin of the magic constant $140$ will be clear shortly.$^\dagger$ We can therefore obtain the recurrence

$$T(n) \leq \begin{cases} O(1)&\quad\text{if $n<140$ $^\ddagger$} \\ T(\lceil n/5 \rceil)+T(7n/10+ 6)+O(n)&\quad\text{if $n \geq 140$ $^\|$}\\ \end{cases}$$

We show that the running time is linear by substitution. More specifically, we will show that $T(n)\leq cn$ for some suitably large constant $c$ and all $n > 0$. We begin by assuming that $T(n)\leq cn$ for some suitably large constant $c$ and all $n < 140$ $^{\dagger\dagger}$; this assumption holds if $c$ is large enough. We also pick a constant a such that the function described by the $O(n)$ term above (which describes the non-recursive component of the running time of the algorithm) is bounded above by an for all $n > 0$. Substituting this inductive hypothesis into the right-hand side of the recurrence

$$T(n) \leq c\lceil n/5 \rceil + c(7n/10+6) +an$$

$$\leq cn/5 + c + 7cn/10 + 6c +an$$

$$= 9cn/10+7c+an$$

$$= cn+(-cn/10+7c+an).$$

which is at most $cn$ if

$$-cn/10 + 7c + an \leq 0.\tag 1$$

$$\iff c\geq 10a(n/(n-70)) \quad\text{when n>70} $$

Because we assume that $n\geq 140$ $^{\ddagger\ddagger}$ we have $n/(n-70)\leq 2$ and so choosing $c\geq 20a$ will satisfy the inequality $(1)$

---

$$ \dagger \quad \text{The statement here complies with the $\ddagger$ in the recurrence relation} $$

$$ \dagger\dagger \quad \text{The statement here does not comply with the $\|$ in the recurrence relation} $$

$$ \ddagger\ddagger \quad \text{The statement here does comply with the $\|$ in the recurrence relation} $$

---

I could not quite understand this discrepancy, however I did not include the entire algorithm (available in CLRS Section $9.3$) but if incase it is needed please say then I shall include it as well.

Answer 1

It seems that $\dagger\dagger$ is consistent with $\|$. You just need to pick a constant $c$ that is larger than or equal to the constant $\gamma$ hidden in the $O(1)$ notation in the definition of $T(n)$ for $n < 140$ (i.e., the line marked with $\ddagger$).

Then, for any $n \in \{1, \dots, 139\}$, you have $T(n) \le \gamma \le c \le cn$, as desired.