I have a question.
In my book they have the following recurrence:
$T(n) = 3T(\lfloor n/4\rfloor )+\theta(n^2)$
They try to guess that $T(n) = O(n^2)$ and they then use the substitution method to verify the guess. But they don't show the base case? Isn't that necessary?
I think maybe it is because they don't know what happen with $T(n)$ when $n=1.$ ??
In my book they also have the reccurence $T(n)=2T(\lfloor n/2 \rfloor)+n$ and $T(1)=1$
They then guess that $T(n)=O(n \ln n)$ And they use the substitution method to verify it.
They assume that $T(n)=O(n \ln n)$ for all positive m
$T(n) \leq 2( c \lfloor n/2 \rfloor \ln( \lfloor n/2 \rfloor)+n$
$\phantom{T(n)} \leq cn \ln(n/2)+n$
$\phantom{T(n)} = cn \ln(n)-cn \ln(2)+n$
$\phantom{T(n)} = cn\ln(n)-cn+n$
$\phantom{T(n)} \leq cn \ln(n)$
where the last step holds as long as $c\geq 1$.
Ok. They then say: "Mathematical induction requires us to show that our solution holds for the boundary conditions"
$T(1)\leq cl\ln(1)=0$
which is at odds with $T(1)=1$
but then they take advantage of asymptotic notation requiring them only to prove $T(n)\leq c n \ln(n)$ for $n\geq n_0$ where they get to choose $n_0$
Then they replace $T(1)$ by $T(2)=4$ and $T(3)=5$ as base cases in the inductive proof letting $n_0=2$
And my question is:
Why do I have to replace the base case $T(1)$ with $T(2)$ AND $T(3)$? Why not just replace it with $T(2)=4 $
I can derive $T(2)=4$ from the recurrence and then say
$T(2)\leq c2 \ln(2) = c2$
Where $c \geq 1$ and I choose $c\geq 2$
Why do I have to consider $T(3)$ ?