asked 21 Jul '15, 23:21

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
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)
thanks... @ho_oh
(22 Jul '15, 12:58)

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

still need more explanation................. answered 22 Jul '15, 00:08
