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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hint: j is actually the Gaussian sum. $\endgroup$ – kelalaka Nov 17 '19 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 '19 at 10:27
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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks a ton .. :) $\endgroup$ – Turing101 Nov 17 '19 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.