Solving recurrence with substitution method

790 Views Asked by At

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?

enter image description here

1

There are 1 best solutions below

1
On BEST ANSWER

why does $\;T(n) \le d \,n^2\;$ hold as long as $\;d \ge \cfrac{16}{13}\,c\;$?

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$