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.

enter image description here

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$?

  • $\begingroup$ 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})$. $\endgroup$ Apr 10 at 5:40
  • $\begingroup$ @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. $\endgroup$
    – JJJohn
    Apr 10 at 6:08
  • $\begingroup$ 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$? $\endgroup$ Apr 10 at 6:28
  • $\begingroup$ @YuvalFilmus $\lfloor n/4 \rfloor$ guarantees that there will not be a thing like 3.5. $\endgroup$
    – JJJohn
    Apr 10 at 6:52
  • $\begingroup$ Your original post didn’t contain any floors… $\endgroup$ Apr 10 at 10:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.