What is the the time complexity for this particular piece of code?
for ( int i=1 ; i < n ; i++){
for(int j=i ; j < n ; j+=i ){
//do something
}
}
What is the the time complexity for this particular piece of code?
for ( int i=1 ; i < n ; i++){
for(int j=i ; j < n ; j+=i ){
//do something
}
}
Answer:- O(n*log(n))
How ?
Hope this helps!
correct me, if I missed something.
Not sure, but @sandeep_007 's answer seems quite accurate.
Sieve of erastothenes code is similar, and it runs in O(N Log(LogN)) , so i think its same, i.e. O(N(log(logN)), but the difference between O(NlogN) and O(Nlog(logN)) is negligible
(except when calculating this complexity comes in your college exam. There the difference can be as much as between an A and B )
My answer is slightly different from that of @sandeep_007
Answer: O(k*log(k)) where k = n-1
For i=1 inner loop goes from 1 to n-1 i.e inner loop runs k/1 times.
For i=2 inner loop runs for approximately k/2 times.
…and so on till i=k for which inner loop runs only 1 time.
(k/1)+(k/2)+(k/3)+ . . . +(k/k) = k((1/1)+(1/2)+(1/3)+ . . . +(1/k))*
(1/1)+(1/2)+(1/3)+ . . . +(1/k) is \sum_{i=1}^{k} \frac{1}{k} which is harmonic number H_k and H_k = O(log(k))
Hence more accurate answer would be O(k*log(k)) where k = n-1
Seems ok. A better approximation expression would have been
Obviously, O(n*(log(n))) would be bigger than O(n).