[Solved]: How to find the asymptotic runtime of these nested loops?

Problem Detail: 

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 ?

Asked By : Xax

Answered By : Karolis Juodelė

$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$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19480