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 2sum_{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
