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…??***

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. :stuck_out_tongue:

1 Like

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

still need more explanation…

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.

thanks… @ho_oh

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…

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…