JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Time out estimation | Reply
Hi, guys,

I got a question about how to estimate the excution time. say I have an algorithm of O(N*N), what is the upper bound of N so it can excuted within 2 secs?

thanks
Re: Time out estimation (response to post by fxiaohu) | Reply
The rule of a thumb I use, is that computer can do up to 10^8 operations per second. I first read it on USACO training and sticked to it. But I guess TopCoder computers are a bit faster than that...

To answer your question - N < 14.000. (Assuming that the constant factor and other factors are small).
Re: Time out estimation (response to post by fxiaohu) | Reply
I like to calculate the number of operators my program will execute in the worse case and use its cubic root to have an idea about the time it will take. So, for exemple, if I have a O(N^2) algorithm to a problem with limit N=2000, we have (2000^2)^(1/3) ~= 160. So, its equivalent to solve a problem with limit N=160 with an O(N^3) solution.
Usually, I am not afraid of writing such a program if this number is up to ~300. I do this just to compare small numbers.
Re: Time out estimation (response to post by reiracofage) | Reply
Isn’t it easier to compare the number of operations K to 27,000,000 than to compare the cubic root of K to 300?
Re: Time out estimation (response to post by fxiaohu) | Reply
Constraints are not tight so I use simple estimation:

when N <= 10, then both O(2^N) and O(N!) are ok
when N <= 100, then O(N^3) is ok (I guess that N^4 is also ok, but never tried)
when N <= 1.000, then N^2 is also ok
when N <= 1.000.000, then O(N) is fine (I guess that 10.000.000 is fine too, but I never tried in contest)
finally when N = 1.000.000.000 then O(N) is NOT ok, you have to find something better...
Re: Time out estimation (response to post by Betlista) | Reply
Actually, sometimes when N=1.000.000.000, O(N) is ok. For example, when you just add in the loop.
http://www.topcoder.com/stat?c=problem_solution&rm=306577&rd=14243&pm=11227&cr=22682745
Re: Time out estimation (response to post by birbbit) | Reply
heh, I see your failed challenge, I'd challenge it too...
RSS