I was reading CLRS' book on how to use the substitution method to solve recurrences, where they have the following example:

$T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$ where $T(1) = 1$

They assume that $T(n) = O(n \log n)$ and go on to prove it by using induction.

I understand the inductive step, but I do not understand how they find the base case.

For $n=1$ we have $T(1) \leq c1 \log 1 = 0$, which is wrong because $T(1) = 1$. So we can not use $T(1)$ as a base case.

For $n=2$ we have $T(2) = 2T(1) + 2 = 4$, so $4 \leq c2 \log2$. The last inequality holds for every $c \geq 2$.

In the book they write that we also need $n=3$ to be the base case. However, they do not really explain why. Why isn't $n=2$ sufficient?


They do not want $T(1)$ to occur as a base case as it causes troubles. $T(3)$ depends on $T(1)$, so if they didn't take $T(3)$ as a base case in addition to taking $T(2)$ as one, they'd run into trouble when applying the inductive step to $T(3)$ as the hypothesis does not hold for $T(\lfloor{\frac{3}{2}}\rfloor)=T(1)$.

| cite | improve this answer | |

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.