Big-Oh Analysis of For Loop

Question

I have the following for loop:

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

What is the strategy to determine the complexity of this loop?

Answer 1

When dealing with for loops, the strategy is as simple as stacking summations one on top of the other.

Each loop corresponds to a sum, thus the complexity of this function is: $$ \sum_{i=1}^{n}\sum_{j=1}^{i³}j $$ The sums correspond to the first two loops, and the $j$ term accounts for the last one. We can now develop this expressions using the partial sum for arithmetic progressions.

Therefore, the number of operations being done (and thus the complexity of the algorithm) is a function of $n$ pertaining to $\mathcal{O}(\sum_{i=1}^{n}\sum_{j=1}^{i³}j)$.

Answer 2

I was going to make this a comment but it grew too long.

Given that you already understand how to obtain the sum $$ \sum_{i=1}^n \sum_{j=1}^{i^3} j $$ for the number of additions to sum, now you just have to compute the sum explicitly!

The inner sum is easy; use the well-known triangle number formula $\sum_{j=1}^k j = \frac{k(k+1)}{2}$ to get $$ \sum_{i=1}^n \sum_{j=1}^{i^3} j = \sum_{i=1}^n \frac{i^3(i^3+1)}{2}.$$

This remaining sum looks a little hairy, fortunately since all we want is the order we can avoid explicitly computing this by noting that this is equal to $$\frac{1}{2}\sum_{i=1}^n i^6 + \mathcal{O}(i^3),$$ so we can ignore the cubic term.

Then Faulhaber's formula tells us that $\sum_{i=1}^n i^p$ is a polynomial in $n$ of degree $p+1$, hence $$ \sum_{i=1}^n i^6 = \mathcal{O(n^7)},$$ which is the complexity of the entire routine.