How can I justify it formally?

Question

Given the following algorithm:

Function Fun(int n){
int j,k,t=1;
for (j=0; j<=4n^2; j+=4){
     for (k=j; k<=4*sqrt(n); k+=4){
          t+=8;
     }
}
}

I want to count how many times the command t+=8; is executed.

I found, by trying several values for n, that it is executed:

times. But, how can I justify it formally?

Answer 1

As we can see from the outher cycle, $j$ is a multiple of $4$, so let's call $\;j=4j'$

the inner loop goes from $\;k=j\;$ to $\;k=4\sqrt{n}\;$, whit a skip of $4$, so the number of repetition is $$ 1+\left\lfloor\frac{\lfloor 4\sqrt{n}\rfloor-j}{4}\right\rfloor=1-j'+\left\lfloor\frac{\lfloor 4\sqrt{n}\rfloor}{4}\right\rfloor=1-j'+\lfloor\sqrt{n}\rfloor $$ The outer loop goes from $\;j=0\;$ to $\;j=4n^2\;$, with a skip of $4$, so we have $$ \sum_{j'=0}^{n^2}1+\lfloor\sqrt{n}\rfloor-j' $$ but since $j'$ cannot go over $1+\sqrt{n}$, we have $$ \sum_{j'=0}^{\lfloor\sqrt{n}\rfloor}1+\lfloor\sqrt{n}\rfloor-j' $$ If you want to know the exact number, it is $$ \sum_{j'=0}^{\lfloor\sqrt{n}\rfloor}1+\lfloor\sqrt{n}\rfloor-j'= \left(1+\lfloor\sqrt{n}\rfloor\right)^2-\frac{\lfloor\sqrt{n}\rfloor\left(1+\lfloor\sqrt{n}\rfloor\right)}{2} $$ $$ =\frac{\left(2+\lfloor\sqrt{n}\rfloor\right)\left(1+\lfloor\sqrt{n}\rfloor\right)}{2} $$