Time complexity

general
1

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

      }

}

1 Like
2

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.

1 Like
3

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 :frowning: )

4

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

5

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).

6

thanks really!!