# How to find the asymptotic runtime of these nested loops? [duplicate]

i=n;
while(i>0) {
k=1;
for(j=1;j<=n:j+=k)
k++;
i=i/2;
}


The while loop has the complexity of $\lg(n)$ the j value of inner loop runs 1,3,6,10,15... increase like 2,3,4,5,...

But how to find the overall complexity ?

• u r genius @Raphael u r the 1st person to figure it out!!! – Xax Jan 3 '14 at 14:50
• From your comments it seems as if you don't know even the basics of algorithm analysis. Please see many questions of the same kind (1, 2, 3) and our reference questions; they should contain everything you need in sufficient detail. – Raphael Jan 3 '14 at 15:56
• I misread the question earlier; the k++ in the inner loop makes things more interesting. Still, please read the questions I linked and present a more elaborate attempt which we can then work off. – Raphael Jan 3 '14 at 16:00
• Please stop undoing edits that improve the question or its formatting. – Raphael Jan 4 '14 at 19:37
• As I've said before, as long as you don't include an elaboration on your thoughts, it remains a duplicate. – Raphael Jan 5 '14 at 16:48

$j$ satisfies the recurrence $j_k = j_{k-1}+k$. Note that another sequence, $s_k = k^2$ satisfies $s_k = s_{k-1} + 2k-1$.
$$j_k = \sum_{i=1}^k i = \frac 1 2\sum_{i=1}^k 2i = \frac 1 2(s_k+k)$$
This should give you enough to find the largest $k$ such that $j_k < n$.
• @avi, which relation is the second? Are you asking why bother expressing $j_k$ in terms of $s_k$? – Karolis Juodelė Jan 3 '14 at 14:00
• @avi, if the loop was for(k = 1; s_k < n; k++) the complexity would be $O(\sqrt n)$. – Karolis Juodelė Jan 3 '14 at 14:35