Using the substitution method for solving recurrences

I have a question.

In my book they have the following recurrence:

T(n) = 3*T(floor(n/4))+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)=2*T(floor(n/2))+n and T(1)=1

They then guess that T(n)=O(n lg n) And they use the substitution method to verify it.

They assume that T(n)=O(n lg n) for all positive m<n

T(n) <= 2(c*floor(n/2)*lg(floor(n/2))+n

     <= c*n*lg(n/2)+n

      开发者_C百科= c*n*lg(n)-c*n*lg(2)+n

      = c*n*lg(n)-c*n+n

     <= c*n*lg(n)-c*n+n

Where c>=1

Ok. They then say: "Mathematical induction requires us to show that our solution holds for the boundary conditions"

T(1)<=c*1*lg(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)<= c*n*lg(n) for n>=n0 where they to choose n0

Then they replace T(1) by T(2)=4 and T(3)=5 as base cases in the inductive proof letting n0=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)<= c*2*lg(2) = c*2

Where c>=1 and I choose c>=2 

Why do I have to consider T(3) ?

---

First, How to evaluate T(6)? T(6) = 2*T(floor(6/2)) + 6 => T(6) = 2*T(3) + 6 = 16.

Second, they have written that - after n > 3,it becomes independent of T(1) ... so after 1 and before 4 all should given as base cases.

That's why we have 2 enter T(3) also.

Please Comments...