You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 29 Aug '17, 22:09

phantomhive's gravatar image

4★phantomhive
944
accept rate: 0%


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.

link

answered 29 Aug '17, 22:30

sandeep_007's gravatar image

5★sandeep_007
7997
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) utkalsinha6★

thanks really!!

(30 Aug '17, 00:55) phantomhive4★

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

link

answered 29 Aug '17, 22:51

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

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

link

answered 30 Aug '17, 00:46

a_d_i's gravatar image

2★a_d_i
1746
accept rate: 23%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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