# What will be big O complexity for this loop? [duplicate]

I am not able to understand time complexity of this for loop. While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity?

public void function(n) {
for(int i = 1; i< n; i++) {
for(int j =     1; j <= n;  j += i) {
System.out.println("*")
}
}
}


## marked as duplicate by Raphael♦Dec 19 '18 at 11:40

• Also, what do you mean by "jumps certain calculation"? The number of iterations of the inner loop depends strictly on the value of n. – dkaeae Dec 19 '18 at 10:12
The inner loopnever stopped for $$n \geq 1$$ as for the first time i = 0 and j += i never increased the value of j. If we suppose i will be started from 1, for i = 1 the inner loop will be iterated $$n$$ times. for i = 2 as value of j is increased by step size 2, the number of iterations of the inner loop is $$\frac{n}{2}$$. Hence, the computation cost of the program is $$\sum_{i = 1}^{n-1}\frac{n}{i} = n \sum_{i = 1}^{n-1}\frac{1}{i} = \Theta(n\log(n))$$.