Running Time Analysis

Question

Here is the problem:

sum = 0 
for i = 1 to n 
  for j = 1 to i^2
    for k = 1 to j
      sum ++

Using three summations, $\sum_{i=1}^{n} \sum_{j=1}^{i^2} \sum_{k=1}^{j}1$ , I got that the highest degree term would be $n^{6}$, after expanding and adding like terms. I got a result of j. For the second outer summation, I got a result of $1/2(i^4) + 1/2(i^2)$. For the final, inner summation, the result was from n to i = 1 of $1/60n (n+1)(2n+1)(3n^2 +3n +4)$ So, would the answer be $O(n^{6})$ like I had thought, or am I doing something wrong here?

Answer 1

$\sum_{i=1}^n \sum_{j=1}^{i^2} \sum_{k=1}^j 1 = \sum_{i=1}^n \sum_{j=1}^{i^2} j = \sum_{i=1}^n {1 \over 2} i^2(i^2+1) = {1 \over 2} \sum_{i=1}^n (i^2 + i^4)$.

You can compute this explicitly, or just use the fact that $\sum_{i=1}^n i^k$ is of order $O(n^{k+1})$, in which case we get that the above is of order $O(n^5)$.