Showing that $T(n)=2T(\lfloor n/2 \rfloor+17)+n$ has a solution in $O(n \log{n})$, question about base case and assuming n is large?

Question

I am self-studying "introduction to algorithms" and am supposed to show that the recurrence $T(n)=2T(\lfloor n/2 \rfloor+17)+n$ has a solution in $O(n \log{n})$ with the "substitution method", which as far as I have understood is just proof by induction that $T(n) \in O(n\lg{n})$ for all $n \geq n_0 > 0$.

I have read answers of this question here on SE (that I think I understand) and in an answer from Rutgers University (4.3-6) (that I don't fully understand) but neither one seems to provide a proof of the base case. Therefore I wonder if I might have misunderstood something about the substitution method or the linked answers.

I have also read This post on SE where both the calculations in the question and answer seems to me to be very wrong (does not apply inductive hypothesis correctly, redefines constants, faulty use of asymptotic notation in last step in answer)

Previously I have only had to prove recurrence relations like $T(n) = T(\lfloor n/2 \rfloor) + f(n)$ or $T(n) = T(n-1) + f(n)$ where the input to $T$ is monotonically decreasing and $T(1)$ forms a natural recursive base case and the inductive base case would usually be proven for $T(1), T(2)$ or $T(3)$.

What I don't understand about the linked answers
1.) They do not seem to prove any base case for the inductive hypothesis $T(k) \leq ck\lg{k}$ for some $c > 0$.
2.) In the inductive proof, they assume that $n$ is "sufficiently large". This seems invalid to me. If we assume that $n$ is sufficiently large then by implication $\lfloor n/2 \rfloor$ would have to be sufficiently large. Then we would need to ensure that the base case is proven for a sufficiently large input.

How I think the proof would need to go
1.) For some $n_0 \geq 1$ (actually probably $n_0 \geq 33$ as noted below) prove a base case for the inductive hypothesis $T(n_0) \leq cn_0\lg{n_0}$ and if we will assume that $n$ is sufficiently large in the inductive step, ensure that $n_0$ is sufficiently large.
2.) Proceed with the inductive step and the rest of the proof.

My main questions are:
1.) Do we need to prove a base case?
2.) Is it valid to assume that $n$ is sufficiently large in the inductive proof if this is not also ensured in the base case?
3.) Is my proof outline correct?

Considering the form of the recurrence relation, I have come to the intuitive conclusion that the recurrence relation can hit two recursive base cases, $T(33) = -33$ and $T(34) = -34$ and I don't think it is too difficult to prove that no matter the input the recurrence will always eventually stop at one of these cases. Also, if $n > 34$ then $n > \lfloor n/2 \rfloor + 17 \geq 34$ and since $T(34) < T(33) < 0 < c \cdot 33 \lg{33} < c \cdot 34 \lg{34}$, $n_0=33$ and $n_0=34$ works as inductive base cases (induction on $n$) if we assume inputs larger than $34$. I am not sure how to proceed byt if anyone has any thoughts on this feel free to share them.

Answer 1

Of course we always need to prove a base case when we do mathematical induction. Here's why the two linked answers avoid it:

• In practice, if $T(n)$ describes the running time of an algorithm, the recurrence will only hold for sufficiently large $n$, and the algorithm will do something else for small $n$.
• There's a standard way to "fill in" the base case that doesn't really depend on the specific recurrence, when we want to prove asymptotic bounds.
• Computer scientists sometimes care less than mathematicians about mathematical rigor.

What the answers you read show is a statement of the form: "Suppose $n \ge n_0$. Then if $T(\lfloor n/2\rfloor) \le c \lfloor n/2\rfloor \log \lfloor n/2\rfloor$, we also have $T(n) \le c n \log n$." Crucially, nothing in that proof depends on $c$ (or at most puts some lower bound on $c$); it's an arbitrary constant.

Here's a way to give this a base case. Suppose that $T(n)$ has some well-defined value for all $n$. Then choose $c$ to be at least the largest value that $\frac{T(n)}{n \log n}$ takes on when $\lfloor n_0/2\rfloor \le n \le n_0 - 1$. (Note that such a largest value is guaranteed to exist when we assume $n$ is an integer, because then we are taking the maximum of finitely many values.)

Choosing such a value of $c$ guarantees to us that $T(n) \le c n \log n$ when $\lfloor n_0/2\rfloor \le n < n_0$, which can be our base case. Then, the inductive step tells us additionally that $T(n) \le cn \log n$ when $n \ge n_0$. This is all we need to show to conclude $T(n) \in O(n \log n)$.

This argument is often omitted because, as you see, we don't need to know anything about $T(n)$ for it. It's the same every time.

---

The one missing thing that we do always have to check is that there's some solution. There would be problems with the base case that we can't fix by looking only at large $n$ if, for example, setting $n=5$ in the recurrence simplified to $T(5) = T(5) + 1$. In this case, the work you've done to check that all inputs reduce to $n=33$ or $n=34$, and that $T(33)$ and $T(34)$ are well-defined, does this for us. (In practice, people skip this if they are analyzing an algorithm that they already know terminates for all inputs.)