Time complexity

Question

How to analyze this problem

 

For (I=1;I<n;I++)

{

   For (j=1;j<n;j=j+I)

{

Print("℅d℅d", I,j);

}

}

 

Please suggest I'm detail how do we unroll  I & j.

Comments

this may help you

https://gateoverflow.in/228545/ubc-intermediate-algorithm-design-analysis-cpsc-summer-2009

https://gateoverflow.in/228411/test-series-algorithms

https://gateoverflow.in/100616/algorithm

Answer 1

first loop runs n times.

second times runs n/2 times

…………...

…………….

last loops runs 1 times

hence n+n/2+n/3+n/4…………….1

T.C=O(n logn).