×

Time Complexity Calculation

 0  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 1.1k●12●29 accept rate: 6%

 1 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 answered 21 Jul '15, 23:46 3★ho_oh 75●6 accept rate: 33% 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) 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)
 0 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.. answered 11 Sep '15, 22:47 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)
 0 still need more explanation................. answered 22 Jul '15, 00:08 1.1k●12●29 accept rate: 6%
 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:

×245
×224
×115

question asked: 21 Jul '15, 23:21

question was seen: 2,922 times

last updated: 12 Sep '15, 02:32