Complexity theory isn’t required to be a programmer

http://mortoray.com/2015/03/24/complexity-theory-isnt-required-to-be-a-programmer/

by nkurz • 11 years ago

38 76 11 years ago

Veedrac5• 11 years ago

If we’re dealing with collections people tend to mean time complexity, because most collections have a space complexity of O(n). I say most, since a common one, the radix tree, does not.

Does it not? It can't be less than O(n) simply by the pigeonhole principle and it doesn't look like it's more than that.

shin_lao• 11 years ago

A radix tree spreads an entry content over several nodes, reusing nodes with similar contents.

http://stackoverflow.com/questions/20573231/whats-the-space-...

141136• 11 years ago

It's still necessarily got a worst case complexity of O(n) - e.g. consider the case where the contents of nodes are perfectly disjoint. In that instance, you'd require O(n) space.

LukeShu3• 11 years ago

I think your confusion comes from the fact that n does not refer to the number of elements, it refers to the sum of the sizes of all of the elements. Let the number of elements be m, for this discussion.

For elements that have a constant/uniform size, this distinction is pointless. However, for things like strings, there can be a large variance in the size.

Applying the pigeonhole principle informs us that the radix tree has a lower bound of O(m); but remember that O(n) could be quite a bit larger than that. A radix tree works by only storing one copy of duplicated prefixes of the elements; it still has an upper-bound space complexity of O(n), but the expected complexity is lower than that.

SamReidHughes7• 11 years ago

It depends on how your computer works. If pointers are magic O(1) values, then sure. But if you need as many bits in a pointer as necessary to distinguish the total number of pointers, then you don't get an asymptotic size advantage.

Also, using n as the sum of the sizes of all the elements is not normal.

Veedrac5• 11 years ago

That was definitely my confusion, thanks.

z5h• 11 years ago

Complexity theory isn't required when prototyping an application. It is required when engineering an application.

waprin• 11 years ago

Not necessarily. In fact it can get in the way because complexity theory ignores all those ugly little constant numbers. More important than complexity theory is actually doing your own measuring and benchmarking, something I've seen forgotten during engineering attempts far more often.

jerf• 11 years ago

"In fact it can get in the way because complexity theory ignores all those ugly little constant numbers."

No, it doesn't. A given person may be, but the theory does not. It so happens that complexity theory makes heavy use of a mathematical construct, the "big-O notation", that makes it easy to ignore low-order term's impact on a process, but that is a tool it uses, not the totality of the theory.

I assure you that if you walk up to a complexity theorists and say "Your ignoring of constant factors makes your entire discipline worthless!" you're more likely to get laughed at than blow their minds.

You want to analyze the real impact of some algorithm in the face of having Big Ints and dealing with cache issues? Complexity theory is ready for you. I've seen it done. The equations get nastybig fast, but fortunately computer algebra systems can chew right them. Amusingly, in the end you end up doing something very similar to O() anyhow and just start semi-arbitrarily chopping off insignificant terms to figure out what's actually going on in the enormous expression. But this can still be a useful exercise to get a sense of where the low-order terms may be dominating, for how long, and whether there's anything useful to do about it.

inverba• 11 years ago

One thing the author doesn't mention is np-completeness. You need complexity theory to introduce/explain the concept of np-complete problems and I would argue that knowledge of those are necessary for a good programmer. Otherwise you might waste a lot of time trying to find a polytime algorithm for something which (arguably) doesn't have one.

kasabali• 11 years ago

It is sad but true. Complexity theory isn't required to be a programmer, it isn't required to release products and that's one of the reasons why a lot of software product we directly/indirectly use everyday sucks so much.

vezzy-fnord• 11 years ago

I think the main reason for Wirth's law stinging as much as it does, isn't so much because of ignorance of algorithmic complexity. Rather, it's because most programmers (and all the languages, libraries, frameworks and various assorted tools and materials that they use) still operate on a mental model of how computer architecture works that is literally decades out of date.

Mainstream infrastructure hasn't done a stellar job in seamlessly abstracting new hardware features (though compiler construction is still decent there in many regards). The one that has, isn't usually mainstream.

steven2012• 11 years ago

It's not required to be a programmer, much like learning how to drive manual is not required to be a driver.

However, if you want someone to pay you the high salary to be a race car driver, then you better know how to drive manual.

There are plenty of positions where people can program and do programming tasks without a great deal of depth of knowledge in terms of programming. And they can make a living doing this.

moron4hire3• 11 years ago

Bad analogy, Formula 1 drivers use selectable-gear, automatic transmissions. It's more efficient to have a computer run the clutch.

rbanffy2• 11 years ago

True, but a race driver needs the intimate understanding of the dynamics of the car, suspension, engine, transmission, tires and track you start getting when you drive manual and actually feel what the car is doing.

gh02t• 11 years ago

F1 cars use sequential gearboxes, which aren't the same as automatic (actually, they're different from typical manual transmissions as well).

They do have driver-operated clutches, though... actually there's TWO of them, usually the bottom two paddles on the left and right of the wheel. They're only necessary when starting the car from stationary, after that the computer takes over. It's actually notoriously difficult to operate them, if you take a look at this video of Richard Hammond driving an F1 car, he takes several tries to get it moving.

http://www.youtube.com/watch?v=9773pisjCSw

Not to mention, there are other types of highly-paid race car drivers.

tptacek5• 11 years ago

This is to me a deeply weird article.

Thematically, it makes a case for complexity not being important to software development. I disagree, but stipulating that the author is correct, where does that slippery slope end? Virtually no formalized CS knowledge is required to make expert use of Microsoft Excel, which is itself an extremely important programming environment. What parts of CS does this analysis include in the requirements for development? Is it important to know how a hash function works if your language gives you a dictionary ADT? Is it important to understand the memory hierarchy if you're just shuttling things into and out of an SQL database? There's a rather large population of "Rails programmers" and "PHP programmers" that need know very little more than an "HTML programmer" does to get their job done.

But it's the specifics of the argument that really bug me. The author seems to be making a case that even if you understand complexity, it's hard to deploy it in a real application. That idea seems totally alien to me. I don't routinely analyze the complexity of a sort or a shortest-paths graph reduction, but I certainly feel like I benefit from understanding how the typical algorithms used to solve those problems scale with the size of their inputs. Simpler: any time you select a binary tree instead of a hash table for your lookup table because you realize you need range queries or sorted traversal, aren't you leaning on complexity theory?

Alex3917• 11 years ago

Simpler: any time you select a binary tree instead of a hash table for your lookup table because you realize you need range queries or sorted traversal, aren't you leaning on complexity theory?

Only a nominal amount. You probably only need to spend a few hours watching YouTube videos to make these sorts of decisions, or pass a phone screen. Whereas there are entire classes and textbooks that cover only complexity theory.

Software is a weird industry because the best and most famous developers tend to be the ones who make software for other developers. And those folks tend to know a ton about software engineering. But the actual folks using those tools don't need to know all that much, and they're generally the ones making all the money.

judk2• 11 years ago

That goes for anything. A carpenter needs to know wood theory, but doesn't need to know how to genetic engineer new species of trees.

ChikkaChiChi• 11 years ago

I think you do benefit, and I think having at least a grasp of the concepts does make you a better programmer.

However, I don't believe every programmer does need to understand complexity theory from a formalized perspective. I'll tie a loose analogy to a musician who cannot read sheet music, yet can still be a maestro. I think that sometimes some people just think a certain way, even if they (or others) cannot really explain it.

But I think that merely scratches the surface of a deeper issue. Bob (in his analogy) can be a perfectly serviceable programmer for many years and create many good things. But Bob may never reach his true potential because he didn't take the time to grasp the fundamental concepts about what he was telling the computer to do, or how the computer behaved when he did them.

Because Bob never truly understands computational complexity, maybe Bob never reaches his true potential.

rbanffy2• 11 years ago

I certainly feel like I benefit from understanding how the typical algorithms used to solve those problems scale with the size of their inputs.

Spot on. Not only that, having that kind of understanding has prevented me from making some really stupid programming mistakes in the past.

One may not need that to write a CRUD (or let your framework of choice do it for you) but if one goes beyond the trivial, it's good to know where one is going.

Having said that, the specific enchantments, peculiarities, poor decisions and sadistic, inconsistent choices of the different tools I use for my work take up much more time and brain power than complexity theory. The inherently complex stuff is relatively rare. What's left is the stuff that's complicated for no good reason.

btilly• 11 years ago

I believe that the author is basically right.

More precisely, I think that there are three types of programmers. Those who don't know the formal theory. Those who know it but don't think in terms of complexity except when they have to. And those for whom big-O is second nature.

I believe that there is great value from having someone around who falls into the third group. (That's where I'd rate myself.) But they are rare. And there is little difference in practice between people in the first and second groups. Exactly how little difference is demonstrated by the fact that people who once took CS and then work as programmers find their memories of big-O fading over time because they aren't using it.

As for where the slippery slope ends, given the choice of having a new developer be a typical CS grad versus a beginning programmer who has mastered everything in Code Complete, I'd go for the second one every time. Obviously this isn't true if you're in an area that requires CS knowledge. But for most working developers, I think it is.

ExploitsforFun• 11 years ago

A developer will hit complexity theory the minute he or she starts to ask the question of "How can I make this process go faster".

zimpenfish2• 11 years ago

But for a high percentage of developers, they'll likely never need to ask that question. The world isn't Facebook and Google and WhatsApp - it's chuggy little Java apps running on crappy PCs shoehorned into server roles outputting horrible HTML for IE7 users to check their trades once a day. If slow code brings in money, it can stay slow as far as I'm concerned.

chrismcb• 11 years ago

The author is correct, you don't need to know complexity theory to be a programmer. But you do need to know it to become a good programmer.

zimpenfish2• 11 years ago

That rather depends on your definition of 'good', no? Which is a whole can of worms we probably shouldn't open.

crimsonalucard5• 11 years ago

In english we tend to use complexity to refer more to how intricate a system is rather then algorithmic run time. It's confusing because programming is involved with the intricacy of systems in a big way. That's why imho, the word 'complexity' is actually a really bad naming choice. Typically when I refer to complexity, I refer to it as complexity in Design and structure.

Programming deals more with this type of design complexity for which currently no theory exists. How do quantify whether one program is more intricate then another? How do we quantify whether the functional style is less complex then an object oriented style? There's no way. Since no theory exists, it largely comes down to using intuition and design to deal with complexity. In short, no theory required, only because no theory exists (yet).

tptacek5• 11 years ago

Isn't that just another facet of the same concept? The property you're referring to as "intricacy" is quantifiable and scales with the kinds of problems a program solves.

crimsonalucard5• 11 years ago

How is it quantifiable? Which is more intricate, Linux or Windows? I don't think that question is answerable in any way that's meaningful. If you ask anyone that question you get a lot of qualitative descriptions and opinions, nothing definitive.

SilasX2• 11 years ago

That's still expressible through computational complexity -- in this case, you're talking about how many components of the system you have to change at in order to change one functionally-distinct thing, and how it scales with the number of components.

Well designed systems allow you to change one module and leave everything else alone -- O(1). Others might require a change on both sides of an interface and be potentially O(n). Still others might require you to to test far-distant parts of the system because they leak an abstraction, and be O(n^2), making them hard to add on to.

You can then characterize "difficulty of changing stuff" as the number of components increase, and it's right back to the format of a computational complexity problem.

crimsonalucard5• 11 years ago

Still others might require you to to test far-distant parts of the system because they leak an abstraction, and be O(n^2)

I don't understand how the theory converts. How is it O(n^2)? How does changing and testing modules convert to this number? Describe a case thats O(n log n).

vancan1ty• 11 years ago

Algorithmic run time is "time complexity." There are many different types of complexity which we can measure in some sense, including space complexity, energy complexity, circuit complexity, and architectural complexity.

http://en.wikipedia.org/wiki/Computational_complexity_theory

I agree with you that there seems to be no foolproof way to measure the overall "software complexity" of a piece of software. There are a lot of methods proposed, but none is provably optimal or even all that useful it seems. Search "Evaluating Software Complexity Measures" by Elaine Weyuker for a somewhat dated paper discussing the topic. I would be very interested if anyone had any recommended resources on the current state-of-the-art regarding software complexity measures.

Seems to me the only way to measure complexity absolutely would be some sort of extension of the minimum description length principle -- what is the shortest way we could write the specification for the entire machine + software that runs on it. Of course this seems completely infeasible for any real world task.

j2kun9• 11 years ago

Considering that people were having typical days of programming before complexity theory existed, of course it's not required. I don't know of anybody who seriously claims that it is required.

kristjan• 11 years ago

Complexity theory had been explored, if not deeply, somewhat before what we'd consider "typical days of programming": https://en.wikipedia.org/wiki/Computational_complexity_theor...

j2kun9• 11 years ago

I suggest you read that more closely. There was no theory laid out until the late 60's, and "complexity theory" was not a field until the 70's. On the other hand, there is a long list of programming languages invented in the 50's.

141136• 11 years ago

I'd argue that the definition of computability is an instance of complexity theory, which easily predates what we'd call "programming".

j2kun9• 11 years ago

Definitely not. Nobody in mathematics considered the efficiency of Turing machines until the late 60's.

iphone7166• 11 years ago

Yes you could get things done most of the time without knowing it, but why bother? It is not hard to learn and you'll need it anyways someday if you code enough.

moron4hire3• 11 years ago

I think programmers should need to know complexity theory, because if there is a "programmer" type job that can be done without knowing it, then we should be working hard to eliminate that job through automation. In other words, dissolve the class of programmers that supposedly don't need to know complexity theory.

Also, big-O is not the be-all, end-all of complexity theory. What a ludicrous sentiment.

j2kun9• 11 years ago

Unfortunately, nobody has yet figured out how to automate the process of encoding arbitrary sets of business rules written by non-programmers into code.

moron4hire3• 11 years ago

The problem isn't that the tools don't exist. The problem is that the work is organized to make someone not-the-manager think about the details. It's not just "arbitrary" business rules that need to be encoded, it's "poorly defined, poorly thought-out" business rules.

That's why SQL didn't take off as a lay-person interface to databases; even though it was meant to be a system anyone could use, you can't get around the fact that you still need to know what you want and what comprises what you want. Your typical middle-manager type knows neither.

That's also why UML can't be converted to a program: if it did, it would call managers out on their inconsistent logic and the manager would just give up and make someone else do it. The fact that it doesn't compile is a feature, one that enables UML to make managers feel like they are being a part of the technical process.

It's not a technical problem, it's a cultural one.

serve_yay• 11 years ago

Indeed, you don't!

And we all look forward to your app being featured on http://accidentallyquadratic.tumblr.com :)

j2kun9• 11 years ago

This article betrays the author's misunderstanding of complexity theory. Complexity theory is about finding algorithms which provably optimize some notion of efficiency. Any notion of efficiency. Complexity theory is not equivalent to using asymptotic notation to describe things. In particular, when you find an algorithm that has, say, O(n) worst-case runtime, then you know that the time-complexity of the problem you're trying to solve is O(n). It could be better, like O(log n), and the goal of complexity theory is to do better or prove you can't. You could also try to find the query complexity of a learning problem in terms of the accuracy desired, or the round complexity of a problem solved by MapReduce algorithms in terms of the number of processors and the size of the input.

How does the algorithm perform in concurrent computing? Clearly we’d prefer an algorithm that can scale over processors to one that can’t ... Certainly there is a way to put this all together in theory, but I don’t know those details.

There are no details to know. Any time you have any parameter of any system which can grow (processors, input size, time, space, cache layers) you can describe anything depending on that parameter using asymptotic notation to get a rough estimate of its efficiency. This is not a question of complexity, just a question of how to express growth rates succinctly. Knowing how to reason about rough estimates is essential for engineers because they have to have some idea about why the thing they're building will conform to specifications at least in principle before devoting the resources to measuring it precisely.

And to reiterate: none of this has anything to do with complexity theory except that in complexity theory we happen to use asymptotic notation very heavily. The author's problem is with mathematical language being used in the workplace.

tptacek5• 11 years ago

Yes, that's a compelling point, but to be clear: he's saying that the asymptotic analysis is itself not useful to programmers. We don't even reach the question of whether the field of complexity theory is relevant to programmers.

j2kun9• 11 years ago

Exactly. He's using the wrong words to describe his point, which is that he doesn't think this particular mathematical language is useful. To someone who is fluent in that language, he makes it clear that he doesn't know how to use the language effectively (to stretch it, at times it doesn't seem like he even understands the semantics). But indeed, how could any sort of language be useful unless you know how to use it effectively?

aruss• 11 years ago

I don't know why we keep passing around this kind of anti-intellectual, faux-controversial drivel. Very little is required to be a programmer (whatever it means to be a programmer). No, you don't need to be an expert on algorithm analysis or complexity theory or some other CS theoretical thing to be a programmer, but it's quite obviously better to be able to reason in a certain way about certain problems (and of course asymptotic analysis isn't everything when dealing with practical applications).

Crito2• 11 years ago

"I don't know why we keep passing around this kind of anti-intellectual, faux-controversial drivel."

There is a rather vocal minority in this community who think that attending universities is a waste of time. These people are naturally interested in notion that things commonly taught in universities, but frequently glossed over when self-teaching or at "hacker schools", are not necessary.

alanh• 11 years ago

not necessary

No education is necessary, but that doesn’t make it devoid of value. Speaking as a US citizen, I truly believe what my country and countless others around the globe desperately need is better and accessible education, absolutely including the Arts.

The opposing viewport can likely be called anti-intellectual in fairness.

dgomez1092• 11 years ago

I would agree with your first statement. I do not agree with the authors proposition that you do not need to understand a bit more than just the surface of something like complexity theory in order to be a good programmer. Being able to develop software is different paradigm altogether, not being able to fall back on theories and a least minimal understanding of principles, wil llead you to not only forget it, but being able to test such assumptions like discussed is not optimal, especially in a work environment >> considering the agile mindset so revered in Silicon Valley..Thank for allowing my inout but thanks for a interesting article.

chucksmart• 11 years ago

If you distinguish a 'software engineer' from a 'programmer' this article makes sense to me. But the article does not even use the word 'reduction' which seemed to be 90% of what we did for homework in my computational complexity class.

Kenji• 11 years ago

"Consider what O(n) means: nothing. That’s right, if somebody tells me something is O(n) it truthfully tells me nothing on its own."

You, my good sir, are totally mistaken. O(n) is a set of functions that grow at most linearly with n, ignoring constants. O(n) is a rich mathematical notation that tells a _lot_ of things on its own. If someone tells you that something 'is' O(n) what they actually mean is that they have a function that is _an element_ of O(n). Again, a very concise and powerful statement on its own. Of course you can't say "this tree is O(n)" because a tree is not a function. That'd be like saying "this apple is dumb". Don't blame the notation, blame the user.

Complexity theory isn’t required to be a programmer

Related Stories