Solving Recurrence Relations 'Chip & Conquer'
For simplicity, let's assume that $5$ divides $n$
and that $n/2=n-5k$ for some integer $k&gt;0$.

$$ \begin{align*}
   T(n) &amp;= T(n-5) + cn^2 \\
   T(n) &amp;= cn^2 + c(n - 5)^2 + c(n - 10)^2 + c(n - 15)^2 + ... + c5^2 + c0^2 \\
        &amp;= c(n^2 + (n - 5)^2 + (n - 10)^2 + (n - 15)^2 + ... + 5^2 + 0^2) \\
      &amp;\ge c(n^2 + (n - 5)^2 + (n - 10)^2 + (n / 2)^2)
       \ge c(n / 2)(1 / 5)(n / 2)^2) \\
        &amp;= cn^3 / 40
         = (c / 40)n^3 \\
        &amp;= \Omega(n^3) \\
   T(n) &amp;= cn^2 + c(n - 5)^2 + c(n - 10)^2 + c(n - 15)^2 + ... + c5^2 + c0^2 \\
      &amp;\le c(n / 5)n^2
       \le cn^3 \\
        &amp;= O(n^3) \\
\end{align*} $$

We conclude that $T(n) = \Theta(n^3)$.



Let's assume for simplicity that $n/2 = n-2k$ for an integer $k&gt;1$.

$$ \begin{align*}
   T(n) &amp;= T(n-2) + \log n
         = \log n + \log(n - 2) + \log(n - 4) + ... + \log(4) \\
      &amp;\ge \log n + \log(n - 2) + \log(n - 4) + ... + \log(n / 2)
       \ge (n / 2)log(n / 2) \\
        &amp;= \Omega(n \log n) \\
   T(n) &amp;= T(n-2) + \log n
         = \log n + \log(n - 2) + \log(n - 4) + ... + \log(4) \\
      &amp;\le (n / 2) \log n \\
        &amp;= O(n \log n) \\
\end{align*} $$

We conclude that $T(n)=\Theta(n \log n)$.