0
$\begingroup$

This question already has an answer here:

I am not able to understand time complexity of this for loop. While outer loop is O(n) the inner loop jumps certain calculation. How to find the complexity?

public void function(n) {
                    for(int i = 1; i< n; i++) {
                        for(int j =     1; j <= n;  j += i) {
                                System.out.println("*")
                        }
                    }
                }
$\endgroup$

marked as duplicate by Raphael Dec 19 '18 at 11:40

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$ See this question. $\endgroup$ – dkaeae Dec 19 '18 at 10:10
  • $\begingroup$ Also, what do you mean by "jumps certain calculation"? The number of iterations of the inner loop depends strictly on the value of n. $\endgroup$ – dkaeae Dec 19 '18 at 10:12
  • $\begingroup$ Sorry I just made an edit for inner loop. where increment on j is now function of i $\endgroup$ – manismku Dec 19 '18 at 10:14
  • $\begingroup$ The time complexity of your program is not defined because your program never terminates. $\endgroup$ – Alex Smart Dec 19 '18 at 10:24
  • $\begingroup$ Correct. Let me edit. Changed i = 0 to i = 1 $\endgroup$ – manismku Dec 19 '18 at 10:25
0
$\begingroup$

The inner loopnever stopped for $n \geq 1$ as for the first time i = 0 and j += i never increased the value of j. If we suppose i will be started from 1, for i = 1 the inner loop will be iterated $n$ times. for i = 2 as value of j is increased by step size 2, the number of iterations of the inner loop is $\frac{n}{2}$. Hence, the computation cost of the program is $\sum_{i = 1}^{n-1}\frac{n}{i} = n \sum_{i = 1}^{n-1}\frac{1}{i} = \Theta(n\log(n))$.

$\endgroup$

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