×

# Time complexity

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 } }

944
accept rate: 0%

 1 Answer:- O(n*log(n)) How ? by doing dry run, you can see for i = 1 inner loop runs n/1 times, i = 2 loop runs (n-1)/2 similarly for other i's also (n-1)/1+(n-2)/2+(n-3)/3+(n-4)/4 ... .. n(1+1/2+1/3+1/4+ .. .. ) - (1+1+1+1 ... (n-1) times) approximately n*(1+1/2+1/3+1/4 .. ... ) 1+1/2+1/3+1/4 ...1/n = ln(n)+γ+1n−14n2+O(n−4) see here which can be roughly approximated to log(n) so time complexity is O(n*log(n)) Hope this helps! correct me, if I missed something. answered 29 Aug '17, 22:30 799●7 accept rate: 16% Seems ok. A better approximation expression would have been $$(\sum_{i=1}^n \frac{(n-i)}{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)
 0 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 15.4k●1●20●66 accept rate: 18%
 0 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 answered 30 Aug '17, 00:46 2★a_d_i 174●6 accept rate: 23%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×135

question asked: 29 Aug '17, 22:09

question was seen: 198 times

last updated: 30 Aug '17, 00:55