Time complexity for the given code

Question

Question

Find the time complexitty for the given code.

sum = 0
for(i=1; i<=n; i++){
    for(j=1; j<=i; j++){
        if(j%i == 0){
            for(k=1; k<=n; k++){
                sum = sum + k;
            }
        }
    }
}

I know this question is already posted here,But i want to solve it by my own so that i can get the feel of the question.

My approach

For $i=1,j$ will execute $1$ time,k will execute $n$times and hence sum will execute $n^2$ times

For $i=2,j$ will execute $2$ times,k will execute $n + \frac{n}{2}$times and hence sum will execute $(n + \frac{n}{2}) \times n$ times

For $i=3,j$ will execute $3$ times,k will execute $n + \frac{n}{2}+ \frac{n}{3}$times and hence sum will execute $(n + \frac{n}{2}+\frac{n}{3}) \times n$ times

I am clueless to move forward , please help me out !

Answer 1

Assuming that your interest is in investigating the number of times the line of code sum = sum+k

Let $I_p$ be the indicator variable.

$$\sum_{i=1}^n\sum_{j=1}^n I_{j|i}n=\sum_{i=1}^n\left(I_{i|i} n + \sum_{j\neq i}I_{j|i}n\right)=\sum_{i=1}^nn=n^2$$

Remark: Of course there are values of $i$ and $j$ where that line of code is not implemented. The complexity of those would be $\Theta(n^2)$ as well.