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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhat 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?
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.