retagged by
626 views

1 Answer

Best answer
1 votes
1 votes
$a_{n} = \frac{j*(j+1)}{2}$ is the equation being folllowed in inner loop for j.

$\implies 2n = j^{2} + j$

$\implies 2n \geq j^{2} \implies j = O(\sqrt{ n})$

Now the while loop is executing $logn$ times giving total complexity = $O(\sqrt{n}logn)$
selected by

Related questions

0 votes
0 votes
2 answers
1
Gate Fever asked Sep 27, 2018
1,925 views
0 votes
0 votes
1 answer
2
0 votes
0 votes
3 answers
3
1 votes
1 votes
2 answers
4
srestha asked Aug 17, 2018
1,017 views
What will be TC here?Ans given $O(n^{2})$ , while I am getting $O(n)$