Delete comment from: Stevey's Blog Rants
Regarding the "Big-Oh is useless" comment:
I'll admit, I'm never going to go out and prove the amortized complexity of a splay tree access. But I've done the ACM's ICPC (and similar) a number of times, and it got me into the habit of doing a (very) rought Big-Oh calculation to see whether the solution was plausible for the size of inputs that were expected.
This was actually useful for me just recently. I had reduced it down to a graph problem (and yes, everything's a graph problem), and implemented Dijkstra, but soon needed to extend it to negative weights. That leads to bellman-ford, but the complexity --- O(v*e) --- for it made be think, 'darn, that's too high'. I knew I had a DAG, though, so I researched a bit, and found an applicable variant that got it down to O(v).
The quick rule-of-thumb estimate saved me quite a bit of coding time.
Apr 27, 2008, 11:46:00 PM
Posted to Get that job at Google