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

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 ﬁrst, 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 speciﬁcally, 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.

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.
• Ok I got it. $\dagger\dagger$ is a part of the inductive prove of the substitution method that $T(n)\leq cn.\quad \forall n>0$... And not a restatement of the $\|$ in the recursive definition. Thanks a lot. I was a bit confused as in the statements they refer to both $\dagger\dagger$ and $\|$ as their $\text{"assumption"}$ without specifically mentioning the context of the induction or the recurrence definition. Jun 23, 2020 at 17:55