What is the the time complexity for this particular piece of code? for ( int i=1 ; i < n ; i++){ asked 29 Aug '17, 22:09

Answer: O(n*log(n)) How ?
Hope this helps! correct me, if I missed something. answered 29 Aug '17, 22:30
Seems ok. A better approximation expression would have been $$(\sum_{i=1}^n \frac{(ni)}{i}) + O(n)$$ Obviously, $O(n*(log(n)))$ would be bigger than $O(n)$.
(29 Aug '17, 23:28)
thanks really!!
(30 Aug '17, 00:55)

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 :( ) answered 29 Aug '17, 22:51

My answer is slightly different from that of @sandeep_007 Answer: O(k*log(k)) where k = n1
Hence more accurate answer would be O(k*log(k)) where k = n1 answered 30 Aug '17, 00:46
