infoarena

http://www.infoarena.ro/blog/numbers-everyone-should-know

This is awesome.

Towards the end of my programing contests career I used to know this list, but not because someone told it to me but because of experience.
Also I think there are also several exceptions to the rule. For example topcoder problems always have n=50. Also one of the best experiences I had solving a task was on the task called "tgraf" from infoarena where I managed to figure out the solution because of the restricion on n (n was maximum 20).

Yes. Lots of problems have multiple parameters (graph algorithms, knapsack, etc) which I skipped in this article. Also there are subtleties in the constant factors. For example not all n^2 algos are alike. One that iterates through a matrix vs one that does just some math operations are pretty different. Also some optimization may significantly change the average case behavior.

I was thinking it would be fun to tag more execution times, complexities, algorithms and datastructures and then play with this table:

find all algorithms with some execution time
find all algorithms for a given data structure
find all data structures for a given complexity

@Igor: because more often than not, in real case backend scenarios, I/O, network and DB access are the bottlenecks in performance, and it's rare that CPU is the limiting factor. This becomes more of a problem in client-side applications, but those are increasingly dumb fronts to fancy backends that do the work.

I've had quite a bunch of programming contest experience, but I've managed to forget most of these times in the meantime simply because i've only rarely had to use them.

I don't think we could exactly determine the amount of data that can be processed in one second because it depends on many factors like processing power, OS etc. A few seconds is more accurate in my opinion. Really useful article indeed!

Good comment Andrew. I've added an example about path finding for GPS applications.

edit: I've just read your article. The idea of having named datasets of different sizes it's pretty smart! But for me those names don't mean too much(as they are UK centric) so other than UK and World I have to look the descriptions up to understand the table.

I remember only one thing: a desktop computer nowadays does about 2^27 operations in one second. The other numbres are very easy to derive.

When I estimate quickly the runtime f(n), I tend to work with (lg f(n)), and check if it goes over 27. For your Dijkstra example, I'd say there are <=2^25<=2^(2^5) nodes and <=2^26 edges, so the runtime should be <=2^(26+5), which is over the budget. Of course, this is a back-of-the-envelope calculation (http://en.wikipedia.org/wiki/Back-of-the-envelope_calculation) that you routinely do in a few seconds, not a precise estimate.

Edit: Previous version had nodes/edges in the Dijkstra example swapped.

Yes, you're right. I was meaning going through all permutations.