JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 504 Time out estimation
 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 okwhen 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 okwhen 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...
 Forums Algorithm Matches SRM 504 Time out estimation Previous Thread  |  Next Thread