Is it correct to solve a recurrence equation if the heredity that only works from a certain rank?

32 Views Asked by At

Sorry my title maybe does not describe my question perfectly I had some troubles to formulate it in a short way. Here is an example. I was trying to solve the recurrence equation $T(n) = 4*T(⌊n/2⌋)+cn$ ( c being a constant ). I made the hypothesis of $T(n) = θ(n²)$ I want to show that this is true using the substitution method. I proceed separately for Ω and O, starting with Ω, I supposed we have $T(m) >= c'm²$ for any m < n and for c' a constant > 0 then I wanted to prove it for n so I did this : $T(m) >= 4c'(⌊n/2⌋)²+cn >= 4c'((n-1)²/2))+cn = 4c'((n²-2n+1)/2)+cn = (4c'n²-8c'n +4c')/2+cn = 2c'n²-4c'n+2c'+cn = 2c'n²-4c'n+2c'+cn >= c'n²$ But the last inequality work only from a certain rank n ( at least I guess it work from a certain rank n, don't hesitate to tell me if this is wrong, I justify it by saying that -4c1n is o(n²) so it will be "annulated" by one of the c'n² in the long term ) but if I think to it, this does mean that the recurrence heredity is only true from a certain rank, it means that even if you prove the base's cases from let's say 1 to a certain x, maybe x is before the first p such $(T(p) <= c'p²) ⇒ T(p*2) <= c'(p*2)²$, do you see what I mean ?