Complexity Matters

On CeePlusPlusSux, DanGreen comments, "I suspect MooresLaw will put an end to the argument within the next decade and understandability will be the only factor"

This doesn't seem to be born out by my experience of machines. Requirements expand to strain the hardware available. In ten years we'll be butting heads with hardware just as much as today. One day we'll run out of physics, and then complexity constraints will matter even more. But programmers who don't understand how to evaluate AlgorithmicComplexity are regrettably all too common. -- PeterMerel

DanGreen's quote was about the choice of language, not the choice of algorithm. When I move the implementation of an algorithm from one language to another, is the complexity affected? (Real question, not a rhetorical one) -- FalkBruegmann

Ah, you're right, apologies to Dan for quoting out of context. As to implementations and languages, of course the first concern is whether the language is compiled or interpreted - no algorithm is going to be a speed demon if you code it entirely in, say, TCL. But in general I guess choice of language is orthogonal to choice of algorithm. -- PM

I just can't see how choice of language is orthogonal to choice of algorithm. Perhaps I'm thinking of algorithm in too wide a sense, but how would you do functional composition and delated evaluation of closures in C/C++?

I'd create some closure objects and then go on from there. Or more likely I'd AlternateHardAndSoftLayers with a language that made that easier. Certainly some languages make some algorithms easier than others. HorsesForCourses.

Quite the contrary, I assert that choice of language restricts the solution space that you can even consider thinking about. After all, a language which doesn't teach you to think differently is not worth learning... -- AlainPicard

That's pretty true. Some algorithms/patterns/designs are just too complex to implement in some languages... curried callbacks for example are pretty hard in Basic, tolerable in C and trivial in Python. -- MartinPool

You could always write an interpreter of a given language in any other given TuringComplete language and then write the algorithm in the interpreted language! Wheeeee...

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of CommonLisp. -- (GreenspunsTenthRuleOfProgramming)

I just spent the last five hours--and most of the last week--analyzing algorithms, inventing new algorithms, proving algorithms are correct. Well, you come up with an algorithm that finds the median of k sorted arrays of size n in O(k*[logn]^2) time and then tell me your mind doesn't hurt.

And you know what? Complexity usually doesn't matter because most problems aren't large enough for the optimization to matter. I'd rather do it in O(kn) time if kn is sufficiently small (say, <10e6) because the code is simpler. It's even simpler in O([klogn]^2) time.

At a recent interview, I was asked what my favourite algorithm was. My answer was linear search. I use it all the time (even in arcane ways, e.g. CollectionAndLoopVsSelectionIdiom), it's simple, I always get it right and it works. -- SunirShah (P.S. I got the job!)

Congrats Sunir! Yes, complexity often doesn't matter ... until it does. But first DoSimpleThings, and always Code First, OptimizeLater. And so on. -- PM