I just started reading the Introduction to Algorithms textbook (CLRS) and they introduced the substitution method when solving Divide and Conquer algorithm. In the final statement, I am confused as in the last step, why does T(n)<=dn^2 holds as long as d >= (16/13)c?. Can someone explain?
2026-04-15 13:08:35.1776258515
Solving recurrence with substitution method
790 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1

If $\;c \le \cfrac{13}{16}d\;$ then $\cfrac{3}{16}dn^2+c n^2 \le \cfrac{3}{16}dn^2 + \cfrac{13}{16}d n^2 = \left(\cfrac{3}{16}+\cfrac{13}{16}\right)dn^2 = dn^2$