Data Structures, Algorithms, & Applications in C++
Chapter 19, Exercise 9
We shall make use of the identity
(sum from i=1 to n)i2 = n(n+1)(2n+1)/6.
(sum from s=1 to q-1)s(q-s+1)
= (q+1)(sum from s=1 to q-1)s - (sum from s=1 to q-1)s2
= (q+1)q(q-1)/2 - (q-1)q(2q-1)/6
= q(q-1)(3q+3-2q+1)/3
= q(q-1)(q+4)/3
= Theta(q3)