Counting amount of Iterations

Question

I'm given a question as such:

How many floating point multiplications are performed when each of the 
following code fragments is executed? Express your answers in terms of n, n>= 10.

for(i=0; i<n*n; i++)
    for(j=0; j<=i;j++)
        a[i][j] = a[i][j]*0.125;

This is for my discrete math class, I'm not sure about how to tackle such a question, any ideas?

Answer 1

Outer loop is executed $n^2$ times.

Inner loop is executed $1, 2, \dots, n^2 + 1$ times.

Therefore, in total there are $\frac{1}{2} (n^2 + 1)(n^2 + 2)$ floating point multiplications.

Answer 2

Let's derive $T(n)$, the runtime function. The outer loop executes $n^{2}$ times, given by the summation:

$$\sum_{i=0}^{n^{2} - 1}$$

The inner loop executes $i+1$ times given by the summation $\sum_{j=0}^{i}$. Each iteration of the inner loop operates in $O(1)$ time, which I will just denote as the constant $c$. So we have:

$$T(n) = \sum_{i=0}^{n^{2} - 1} \sum_{j=0}^{i} c = \sum_{i=0}^{n^{2} - 1} ic = c \sum_{i=0}^{n^{2} - 1} i = \frac{c}{2} n^{2}(n^{2} - 1) = \Theta(n^{4})$$