Analyze and find the solution Un in $u_k=u_{k−1}+k^2$ recurrence relation in terms of Big Theta

Question

I am trying to analyze this recurrence relation in terms of Big Theta. Why $\Theta(N^2)$ is wrong answer? My thought is that while the answer for a similar problem is $u_k=u_{k−1}+1 = \Theta(N)$ then the answer for the problem above must be $\Theta(N^2).$ I am following the method of finding the $\Theta$ in a non recurrence function.

Answer 1

To see for yourself, expand your recurrence relation:

$$ \begin{align} u_k &= u_{k-1} + k^2 \\ &= \underbrace{u_{k-2} + (k-1)^2}_{= u_{k-1}} + k^2 \\ &= \underbrace{u_{k - 3} + (k - 2)^2}_{= u_{k-2}} + (k - 1)^2 + k^2 \\ &= \underbrace{u_{k - 4} + (k - 3)^2}_{= u_{k-3}} + (k-2)^2 + (k - 1)^2 + k^2 \\ & \vdots \\ u_k &= u_0 + \sum_{i=0}^k (k - i)^2 \\ &= u_0 + \frac{k(k + 1)(2k + 1)}{6} \\ &= u_0 + \frac{k^3 + \mbox{terms dominated by } k^3}{6} \end{align} $$ which, assuming $u_0$ takes constant time, is essentially $\mathcal{\Theta}(k^3)$. Remember that $T(n) = \Theta(n^3)$ is implied by

$$ c_1 n^3 \leq T(n) \leq c_2 n^3 $$ for appropriately small $c_1$ and large $c_2$, which is the case here.

Answer 2

It seems easier to me to solve the recurrence and analyze the solution.

First we try to get rid of the inhomogenity: $$ u_k = u_{k-1} + k^2 \\ $$ Then for $k+1$ we have $$ u_{k+1} = u_k + (k+1)^2 \\ $$ Then subtracting the first equation from the second and rearranging gives $$ u_{k+1} = 2 u_k - u_{k-1} + 2k + 1 \\ u_{k+2} = 2 u_{k+1} - u_k + 2k + 3 $$ and subtracting again gives $$ u_{k+2} = 3 u_{k+1} - 3 u_k + u_{k-1} + 2 \\ u_{k+3} = 3 u_{k+2} - 3 u_{k+1} + u_k + 2 $$ and finally $$ u_{k+3} = 4 u_{k+2} - 6 u_{k+1} + 4 u_k - u_{k-1} $$ or $$ u_n = 4 u_{n-1} - 6 u_{n-2} + 4 u_{n-3} - u_{n-4} $$ This is a homogeneous linear recurrence relation with constant coefficients and characteristic polynomial $$ p(t) = t^4 -4 t^3 + 6 t^2 - 4 t + 1 = (t-1)^4 $$ with four fold root $r=1$ and thus the solution is of the form \begin{align} u_n &= k_1 r^n + k_2 n r^n + k_3 n^2 r^n + k_4 n^3 r^n \\ &= k_1 + k_2 n + k_3 n^2 + k_4 n^3 \end{align} The four constants $k_i$ depend on the initial values $u_1, u_2, u_3, u_4$.

Thus $u_n = \Theta(n^3)$.