1
$\begingroup$

While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem.

enter image description here

Why we assumed that this inequality holds for all positive $m<n$, in particular for $m=\lfloor n/2\rfloor$? on what basis do we choose this $m$ and why do we need it. Appreciate your answers.

EDIT: Excerpt is from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

$\endgroup$
2
  • $\begingroup$ Are you familiar with complete induction? $\endgroup$ Jan 30 '21 at 13:47
  • $\begingroup$ We choose this value of $m$ since this is the value relevant for proving the inductive step. $\endgroup$ Jan 30 '21 at 13:48
1
$\begingroup$

As Yuval has mentioned in the comment that the proof is based on the complete induction.

However, an important thing is missing in the screenshot that you have shared. The "base case" is missing. Without the base case, the induction hypothesis and proof make no sense.

Here, the base case is when $n = 1$. You might want to verify that $T[1] = O(1)$. And, if that is the case, then $T[1]$ satisfies the induction hypothesis, i.e., $T[n] \leq c \cdot n \log n$ for $n = 1$ and sufficiently large $c$. Now, you would like to prove that the hypothesis also holds for other values of $n$.

For this, you assume that $T[m] \leq c \cdot m \log m$ for any $m<n$. And, suppose using this you could prove that $T[n] \leq c \cdot n \log n$. Then, it will imply that the hypothesis is indeed the correct hypothesis for every $n$. This is because you can apply this proof step to the base case. And, it will give you the correctness of the hypothesis on $T[2]$. Then, you apply the proof step on $T[2]$ and it will give you the correctness on $T[3]$, and so on... Therefore, it proves that the hypothesis is indeed the correct hypothesis for all value of $n$, for sufficiently large $c$.

$\endgroup$

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.