time complexity when power is involved in iteration

How do I calculate the time complexity of the following method? Would you please provide explanation? I know it's going to involve sqrt(n) * . I Just don't know what that ` is.

public void timeComplexity(int[] arr){
    int n = arr.length;
    int sqrt = (int) Math.sqrt(n+1);
    for(int i=2; i<sqrt; i++){
        for(int k= (int) Math.pow(i,2); k < n; k+=i){
            //do some constant time work
        }
    }
}

Also consider the following two variations:

• k starts at i (k=i or k=3) instead of k= (int) Math.pow(i,2).






• k is incremented by some constant k++ instead of the variable i k+=i`

You are interested in several different variants. I'll show you how to estimate the running time in the first one, you do the rest. In fact, I will only estimate the number of times that the inner loop is run, which is
$$
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil.
$$
To obtain this, you need to figure out the number of iterations in loops of the form for (x = a; x < b; x += c) (assuming $a \leq b$ and $c \geq 1$), which is a nice exercise.

Using $x \leq \lceil x \rceil < x+1$, we see that the sum above can be bounded by
$$
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i} \leq
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil <
\lfloor \sqrt{n+1} \rfloor-2 + \sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i}
.
$$
Using $m = \lfloor \sqrt{n+1} \rfloor - 1$, we can evaluate the left sum as follows:
$$
\sum_{i=2}^m \frac{n-i^2}{i} = n \sum_{i=2}^m \frac{1}{i} - \sum_{i=2}^m i =
n (H_m-1) - \frac{m(m+1)}{2} + 1,
$$
where $H_m$ is the $m$th harmonic number. It is well-known that $H_m = \log m + O(1)$, and so we can estimate the sum by $\frac{1}{2}n \log n - \Theta(n)$, skipping a few steps. A similar bound holds for the right sum, since the additional term is only $\Theta(\sqrt{n})$. Altogether, we deduce that the inner loop runs $\frac{1}{2}n\log n - \Theta(n)$ many times.

StackExchange Computer Science Q#90063, answer score: 2