1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Abhishek Ghosh Jun 23 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.