substitution method on T(n) = T(floor(n/2)) + n recurrence
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 &quot;base case&quot; 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&lt;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$.