Time Complexity: Big-O

What is the time complexity of this loop?

k=1
for(j=0;j<=n;j+=k)
k++;


Is it $$O(n)$$ as we are increasing $$j$$ linearly?

• Hint: j is actually the Gaussian sum. Nov 17, 2019 at 10:09
• Cant understand, if you can provide an explanation it will be of much help, even I have no answer manual to confirm, nor its an assignment, if I left this without understanding, it will remain like this for me Nov 17, 2019 at 10:27

Here are the values of $$j$$ at the end of each iteration: $$1,3,6,10,15,21,28,36,45,55,\ldots$$ More generally, after $$t$$ iterations, $$j = 1 + \cdots + t = \binom{t+1}{2} = \Theta(t^2)$$. Therefore the loop halts after $$\Theta(\sqrt{n})$$ iterations.