I am currently working through Cormen et al's classic book on algorithms and data structures. I am trying to follow an inductive substitution proof that the following time complexity function is $O(n\circ lg(n))$:
$T(n) = 2T([\frac{n}{2}]) + \Theta(n)$.
I am not quite following the details of his proof. His basic method is this:
$\textbf{Proof Strategy}$
"Suppose that, for all $n'$ such that $n_0 \leq n' \leq n$ we have it that $T(n') = c \circ n' \circ lg(n)'$ (that is, that $T(n) = O(n \circ lg(n))$). Then $T(n) \leq c \circ n \circ lg(n)$."
Now, he show that $T(n) \leq c \circ n \circ lg(n)$ when $n \geq 2\circ n_0$, and then he moves to the base cases. It is here when I lose him. He says:
We have shown that the induction holds for the inductive case, but we also need to prove that the inductive hypothesis holds for the base cases of the induction, that is, that $T(n) \leq c\circ n\circ lg(n) $when $n_0 \leq n < 2n_0$. As long as $n_0 > 1 \ldots$ we have $lg(n) > 0$. So let's pick $n_0 = 2$. Since the base case of the recurrence (shown above) is not stated explicitly, by our convention, $T(n)$ is algorithmic, which means that $T(2)$ and $T(3)$ are constant (as they should be if they describe the worst-case running time of any real program on inputs of size $2$ or $3$). Picking $c = max\{T(2),T(3)\}$ yields $T(2) \leq c < (2\circ lg(2))\circ c$ and $T(3) \leq c < (3 \circ lg(3)\circ c$, establishing the inductive hypothesis for the base cases. (Cormen et al, 2022: 91)
I don't follow the reasoning here on a few counts. First of all, I thought this was a strong induction, so I'm not used to hearing about explicit base cases in a strong induction. Secondly and more specifically, I don't understand why he excludes $T(1)$. The definition of big O allow $0 \leq f(n) \leq c\circ g(n)$. So even if $c \circ 1 \circ lg(1) = 0$, what's the problem, technically speaking?
It seems at this stage the proof switches from fully formal mathematical reasoning to reasoning which involves background assumptions regarding the time complexity of algorithms. I wonder if anyone can help me understand Cormen's treatment of base cases here?
Thanks in advance.