0
$\begingroup$

This question already has an answer here:

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 ?

$\endgroup$

marked as duplicate by Raphael Jan 3 '14 at 15:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ u r genius @Raphael u r the 1st person to figure it out!!! $\endgroup$ – Xax Jan 3 '14 at 14:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Jan 3 '14 at 15:56
  • $\begingroup$ 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. $\endgroup$ – Raphael Jan 3 '14 at 16:00
  • 1
    $\begingroup$ Please stop undoing edits that improve the question or its formatting. $\endgroup$ – Raphael Jan 4 '14 at 19:37
  • 1
    $\begingroup$ As I've said before, as long as you don't include an elaboration on your thoughts, it remains a duplicate. $\endgroup$ – Raphael Jan 5 '14 at 16:48
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ why is the second relation needed can u explain @Karolis $\endgroup$ – Xax Jan 3 '14 at 13:06
  • $\begingroup$ @avi, which relation is the second? Are you asking why bother expressing $j_k$ in terms of $s_k$? $\endgroup$ – Karolis Juodelė Jan 3 '14 at 14:00
  • $\begingroup$ yes ,i cant figure it out .@Karolis $\endgroup$ – Xax Jan 3 '14 at 14:25
  • $\begingroup$ @avi, if the loop was for(k = 1; s_k < n; k++) the complexity would be $O(\sqrt n)$. $\endgroup$ – Karolis Juodelė Jan 3 '14 at 14:35
  • $\begingroup$ total complexity is then O(log n^3/2)@Karolis $\endgroup$ – Xax Jan 3 '14 at 14:45

Not the answer you're looking for? Browse other questions tagged or ask your own question.