# Given T(1)=1 and $T(n) = 3T(n/4) + cn^2$, does it make sense to yield $T(2)=T(1)+c2^2$?

Section 4.4 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" illustrates how a recursion tree provides a good guess for the recurrence

$$T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2) = 3T(n/4) + cn^2$$

where c is a constant.

The authors assume that n is an exact power of 4.

I agree with the tolerable sloppiness and understand the basic idea of that section.

I'd just like to know about some other trivial details.

For convenience, assume T(1)=1, so $$T(4)=3T(4/4)+c4^2=3T(1)+c4^2$$, what about T(2) and T(3)?

Does it make sense to yield $$T(2)=T(1)+c2^2$$?

Similarly, $$T(3)=2T(1)+c3^2$$?

• Your recurrence is only defined for powers of 4. It is undefined for an input which is not an integer power of 4. In particular, $T(2)$ and $T(3)$ are as meaningless as $T(\pi)$ and $T(\sqrt{-1})$. Apr 10 at 5:40
• @YuvalFilmus Per my understanding of the section and some other parts of that book, the recurrence is NOT defined for powers of 4, I prefer that the domain is the set of all positive integers. Apr 10 at 6:08
• If $n$ is not a multiple of $4$, then $n/4$ is not an integer. Can you run your algorithm on a list of length $3.5$? Apr 10 at 6:28
• @YuvalFilmus $\lfloor n/4 \rfloor$ guarantees that there will not be a thing like 3.5. Apr 10 at 6:52
• Your original post didn’t contain any floors… Apr 10 at 10:30