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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Hint: j is actually the Gaussian sum. $\endgroup$– kelalakaNov 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$– Turing101Nov 17, 2019 at 10:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Nov 17, 2019 at 11:33