Solving recurrences and proving bounds
Exercise 7.4-1 Show that the recurrence $T(n) = max\{T(q) + T(n - q - 1): 0 \le q \le n - 1\} + \Theta(n)$ has a lower bound of $T(n) = \Omega(n^2)$. [1] Inductive hypothesis: $T(n) \ge n^2$ $T(n) = max\{q^2 + (n - q - 1)^2: 0 \le q \le n - 1\} + \Theta(n)$ $f(q) = q^2 + (n - q - 1)^2: 0 \le q \le n - 1$ By expanding the expression we obtain $f(q) = q^2 + (n - q)^2 - 2 \cdot (n - q) + 1$ $f(q) = 2 \cdot q^2 + n^2 - 2nq - 2n + 2q + 1$ Now let’s find the local maxima of the function using its first derivative. Taking the first derivative with respect to $q$ we obtain: $f'(q) = \frac {d}{d q}2q^2 + \frac {d}{d q} n^2 + \frac {d}{d q} -2nq + \frac {d}{d q}-2n + \frac {d}{d q} 2q + \frac {d}{d q} 1$ Since we are looking for a critical point in the graph, $f'(q) = 4q - 2n + 2 = 0$ $q = \frac{n - 1}{2}$ This can be either a local minima or a maxima of our function. Let’s determine it next. Let $q = 1$ for sufficiently large $n$, plugging in the values in the above equation we get: $4