$$T(n) = \max_{0 \le q \le n-1} \{T(q) + T(n - q - 1)\} + \Theta(n)$$
The solution presented in my book is as follows:
We guess that $T(n) \le cn^2$ for some constant $c$, then
$$T(n) \le c\cdot\max_{0 \le q \le n-1} \{q^2 + (n - q - 1)^2\} + \Theta(n)$$
and since $\max_{0 \le q \le n-1} \{q^2 + (n - q - 1)^2\} \le (n-1)^2 = n^2 - 2n + 1$
$$T(n) \le cn^2 - 2cn + c + \Theta(n) \le c'n^2$$
So $T(n) \in \mathcal{O}(n^2)$.
I don't understand part where the book guesses $T(n) \le cn^2$, why is this guess correct ?
I can guess $T(n) \le cn$ and arrive at different result, like $T(n) \le c\cdot\max_{0 \le q \le n-1} \{q + (n - q - 1)\} + \Theta(n) \le c(n-1) + \Theta(n)\implies T(n) \in \mathcal{O}(n)$ which is not correct.