Runtime of for loop-Q1

Problem: Find the time complexity for a nested for loop.

1
2
3
4
5
6
7
8
9
10
A() {
    int i, j, k ,n;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= i^2; j++) {
            for(k = 1; k < n/2; k++) {
                System.out.println("hello world"); 
            }
        }
    }
}

For this problem I found that the best approach is to unroll the loops until the inner most loop. The inner most loop is the highest order of magnitude in terms of work. The goal is to find a formula that gives you the additive sum for all the work done. It is best to get familiar with arithmetic series and the best source for this is Khan Academy.

$$ i = 1 \\ j = 1 \\ 1 \times \frac{n}{2} $$

$$ i = 2 \\ j = 4 \\ 4 \times \frac{n}{2} $$

$$ i = 3 \\ j = 9 \\ 9 \times \frac{n}{2} $$

$$ i = 4 \\ j = 9 \\ 16 \times \frac{n}{2} $$

$1 \times \frac{n}{2} + 4 \times \frac{n}{2} + 9 \times \frac{n}{2} + 16 \times \frac{n}{2} ... \\ \frac{n}{2} (1 + 4 + 9 + 16 \; + \; ...) \Rightarrow \frac{n}{2} \times\sum_{i=0}^n i^2 \\ \sum_{i=0}^n i^2 = \frac{n (n + 1) (2n + 1)}{6} \Rightarrow \\ \frac{n}{2} \times\sum_{i=0}^n i^2 = \frac{n (n + 1) (2n + 1)}{6} \\ runtime = \frac{n^2 (n + 1) (2n + 1)}{12}$

Answer: $O(n^4)$