# 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) * <something>. I Just don't know what that <something> 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:

1. k starts at i (k=i or k=3) instead of k= (int) Math.pow(i,2).
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.

• Thank you so much for caring! I was able to follow the explanation very well without any problem. – salyela Mar 31 '18 at 20:06