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

×

Time Complexity Calculation


       for(i=1;i<=n;i++){

              for(j=i;j<=n;j+=i){
                sum+=i;
               }
        }

  • what is time complexity of above question ??

  • can we solve n<=10^7 constraints by this algo??

  • provide more resource to analyze time complexity much more complex....??***

asked 21 Jul '15, 23:21

rcsldav2017's gravatar image

5★rcsldav2017
1.0k1229
accept rate: 6%

closed 18 Aug '15, 01:10


Well, Time complexity seems to be n*ln(n+1) as the inner loop runs for n times for i=1, n/2 times for i=2 and so on till 1 time for i=n. Sum of 1+1/2+1/3....+1/n=ln(n+1) [Lower bound]{There are many proofs on internet for this. You can check this on Quora too}.

Whether the constraints can be passed or not is something that largely depends on the time limit.

Wait for other comments too in order to confirm. :P

link

answered 21 Jul '15, 23:46

ho_oh's gravatar image

3★ho_oh
756
accept rate: 33%

edited 21 Jul '15, 23:55

time limit : 1sec

link for problem...https://www.codechef.com/problems/ALK1105

i know better soution for this problem....

i just want to know why first algo gives tle...O(N)??

(22 Jul '15, 00:04) rcsldav20175★

Because first one has a time complexity of omega(nlog(n+1)) {omega meaning lower bounds}, whereas your second algo has complexity O(n) {Big Oh meaning upper bounds}. Think of n=10^7 [boundary case], your second algo has :at most: 10^7 operations whereas your first algo has :at least: 10^7 * ln(10^7 +1) which nearly equals 16* 10^7 {you can check for yourself}. Now, this value is 16 :times: greater than what your second solution gives. Hence, TLE.

(22 Jul '15, 09:29) ho_oh3★

thanks... @ho_oh

(22 Jul '15, 12:58) rcsldav20175★

you can solve n=10^7. but not everywhere.it may be possible in your pc..but codechef do not supports it... correct if i m wrong..

link

answered 11 Sep '15, 22:47

pranjulsingh15's gravatar image

2★pranjulsingh15
16
accept rate: 100%

Actually now we have Giga hertz processor this is directly imply that we can execute around(10^9) instruction per second..but in real life we can execute around (10^8) easily on online judge too...

(12 Sep '15, 02:32) rcsldav20175★

still need more explanation.................

link

answered 22 Jul '15, 00:08

rcsldav2017's gravatar image

5★rcsldav2017
1.0k1229
accept rate: 6%

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:

×214
×213
×108

question asked: 21 Jul '15, 23:21

question was seen: 2,695 times

last updated: 12 Sep '15, 02:32