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$
-
$\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
$\begingroup$
$\endgroup$
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 '19 at 11:33
