1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Hint: j is actually the Gaussian sum. $\endgroup$
    – kelalaka
    Nov 17, 2019 at 10:09
  • $\begingroup$ 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 $\endgroup$
    – Turing101
    Nov 17, 2019 at 10:27

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks a ton .. :) $\endgroup$
    – Turing101
    Nov 17, 2019 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.