Solving recurrences and proving bounds

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 \cdot 1 - 2n + 2 = 6 - 2n \lt 0$ for sufficiently large value of $n$.

Now let’s plug in $q = \frac{n}{2}$ in our equation:

$2n - 2n + 2 = 2 \gt 0$

Thus, we have a local minimum of our function at $q = \frac{n - 1}{2}$

Given that this is a continuous function, our local maxima should lie at the boundary points of the function where $q = 0$ and $q = n - 1$

Both of these $q$ values lead to the following recurrence.

$T(n) = T(0) + T(n - 1) + \Theta(n)$

Now let’s solve this recurrence using the substitution method.

Let $T(n) \ge c \cdot n^2$ for some constant $c \gt 0$.

Plugging into our equation we then obtain

$T(n) \ge c \cdot (n - 1)^2 + \Theta(n)$

By expanding brackets, we then obtain

$T(n) \ge cn^2 + c + n \cdot (1 - 2c)$

$T(n) \ge cn^2 $

And this holds for $0 \lt c \le \frac{1}{2}$ for some constant $c$.

Thus, $T(n) = \Omega(n^2)$

And that concludes our proof.

Ravindra Ranwala's Blog