7.4-1

Show that in the recurrence $T(n) = max_{0 \leq q \leq n- 1} (T(q) +T(n-q-1))+ \theta(n),$ $T(n) = \Omega (n^2)$ Let us use assumption method $$T(n) \geq c n^2 $$ $$T(n) \geq c q^2 + c (n-q-1)^2+ \theta(n) $$ $$T(n) \geq c q^2 + c (n-q-1)^2+ \theta(n) $$ for T(n) to be greater than or equal to right side of the equation we need to see if this hold at maximum value of the term $q^2 + (n-q-1)^2$. The maximum for term occurs when q = 0,n-1. By substituting either one we get $(n-1)^2$. $$T(n) \geq c (n-1)^2 + c + \theta(n)$$ $$T(n) \geq c (n^2-2n+1) + c + \theta(n)$$ $$T(n) \geq c (n^2)+ c (-2n+2) + \theta(n)$$ if we pick a large value for c so it can dominate $\theta(n)$. $$T(n) \geq c (n^2)$$ $$T(n) = \Omega(n^2)$$