Time complexity enough for AC or TLE?

I have an O(n^2) algorithm and n<=10^4. Will it pass the servers or will it give TLE?

Quick survey:

What do you think is this agains the rules?

See http://discuss.codechef.com/questions/855/what-kind-of-comment-should-i-post-on-the-problem-page

You cannot share the run-time or space complexity of your solution

I’m not really 100% sure…

The estimation you can use is, that computer can do about 1 billion operations in 1 second. But thats just rough estimation.

You may have idea of time using this table also , the data is for N =100
Approximate completion time for algorithms, (source - topcoder)

O(Log(N)) 10^-7 seconds

O(N) 10^-6 seconds

O(N*Log(N)) 10^-5 seconds

O(N^2) 10^-4 seconds

O(N^6) 3 minutes

O(2^N) 10^14 years.

O(N!) 10^142 years.

2 Likes

Depends on Time Limit .

Did I say which question was I referring to? Did I even say anything remotely related to a XYZ solution to a ABC question? I am just overall curious about the speed of the codechef servers.

I also wanted to know whether an O(n^3) would pass for n<=10^3.

@asif_mak say it is 1 second? Will it pass? And if it is 2 seconds? Just curious.

Just try it out :stuck_out_tongue:

1 Like

@ajinkya1p3 I don’t want to waste my time coding a solution that is bound to give me TLE. Rather that time will be well spent thinking a better solution :). But I guess there is no other way.

1 Like

Hope for weak test cases and it will pass…

I think you would know it better than me @betlista that Codechef doesn’t give you an AC so easily. :stuck_out_tongue: Weak tests are rare, that’s what makes Codechef good.

he might want to say that log N takes 10^(-7) seconds for N=100.

10^-7 seconds i mean ,

see it here , please donot downvote as it decreases my karma or reputation without any reason.

Wow, very bad formatting also on TopCoder page…

2 Likes