Complexity theory isn’t required to be a programmer | Hacker News Reader

Complexity theory isn’t required to be a programmer

mortoray.com

38 pointsnkurz76 comments

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?

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.

> 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.

> 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.

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.

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.

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

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".

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.

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.

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.

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.

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?

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).

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.

> "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.

> 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.

Perhaps I should have mentioned that I am not a member of this minority.

If I am hiring for a developer position, I consider at least a basic knowledge of complexity to be necessary. There are too many developers who are familiar with it for me to waste my time on ones that are not.

I am not speaking of "necessary" in a universal sense, since that would be nearly impossible to define and a useless concept even if we could. If we really get down to it, breathing isn't necessary...

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.

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

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.

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.

Indeed, you don't!

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

"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.

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.

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.

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

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.

"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.

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.

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

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.

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.

> 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.

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.

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.

    > If pointers are magic O(1) values

Um... pointers are O(1) size. Usually either a fixed 32 or 64 bits.

    > then you don't get an asymptotic size advantage.

I even said that! I specifically said that it's still O(n) upper bound, but that the expected case is lower than that.

Though to be fair, I should have written Ω(m) instead of O(m) when discussing the lower bound.

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

1. I didn't say it was normal; just that in this case, that's what it was referring to.

2. It is though! Worded another way, n is the size of the data being stored.

>Um... pointers are O(1) size. Usually either a fixed 32 or 64 bits.

If you want to talk about asymptotic growth of an algorithm, you need it defined on a machine model that supports infinite memory. Saying that pointers are special O(1) size values are a reasonable way to do that. Another way is to let them be variable size, and include that cost in your measurements. With your 64-bit pointers, you're overpaying that cost. And the transition from 32 bit pointers to 64 bit pointers is an object lesson on the real existence of this logarithmic factor that you'd like to pretend doesn't exist.

Edit: also, going with O(1) pointers, the expected asymptotic space usage doesn't mean anything without specifying the probability distribution of dictionaries involved (maybe parameterized on the size n). It's not hard to construct one that changes the outcome.

Ok, fair.

It would have been correct for the original author to have written that most collections have ϴ(n) space complexity, where radix trees only have O(n) space complexity.

It's common for people to use O when they mean ϴ or Ω. All the original statement was saying is that most collections use as much data as you put in, but some (like radix tree) can use less.

(for fun, if we don't give O(1) pointers: If I'm not mistaken, radix tree has O(m*log(m)+n), Ω(m) space-complexity, which is O(n) iff the average size of an element is ≥ log(m); which it almost certainly would be)

> which is O(n) iff the average size of an element is ≥ log(m); which it almost certainly would be

That's stronger than a mere "almost certainly". At least some constant fraction (dependent on the alphabet) would be of size Ω(log m) for some base also dependent on the alphabet, so the average size is also Ω(log m).

I'm not sure how you get your best case, though. It seems to me that the best case has at least Θ(m) nodes since there are m contained strings. The best case for this is each being of minimum size - which is constant size. Each node but the first has a pointer to it of size Ω(log m), so the overall minimum cost is Ω(m log m).

That was definitely my confusion, thanks.

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

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

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.

With a finite alphabet (which is necessarily the case in complexity theory) the contents of nodes cannot by perfectly disjoint.

Ah yes, you're right - I messed up, and was thinking in terms of strings of symbols, in which case there can be an infinite number.

EDIT:

Sorry, wait, I was correct all along - as I was talking about the worst case complexity! Consider the case when our alphabet is {A,B}, and I want to store the strings "A" and "B", in that case, I have to use O(n) space, as I'd need at least two nodes for the two strings.

No. You have to look at infinite subsets of the input space in order to show a counterexample of a Big-O claim. In particular, choose an input for each input size n, let f(n) be the space usage of the radix tree for that input, and show that f(n) is in Theta(n) or at least that it's not o(n).

Technically only finite subsets of unbounded size.

Huh? No?

Here the input space is a set of dictionaries. A dictionary is a finite set of strings. A subset of the input space is a set of dictionaries.

Finite subsets of the input space are finite sets of dictionaries, thus they have bounded size.

Nevermind, I thought you meant something else. To be fair, though, your input doesn't have to be arbitrary subsets of a space. You could require, say, that all strings in the radix tree are about the same size.

> You could require, say, that all strings in the radix tree are about the same size.

That's just a specification of an arbitrary subset of the input space.

(I misread your last comment :-)

It doesn't matter though, it's still O(n) worst case (where n is the total size of the data).

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.

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.

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.

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...

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.

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

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

Did I say anything about efficiency? Computability itself is a topic within computational complexity, as (in many ways) it's one of the "hardest" rungs of the complexity ladder.

I'm sorry, but you're wrong. Complexity theory is by definition the subfield of computer science that studies the efficiency of algorithms, or the inability for algorithms to meet certain efficiency requirements.

This is my field of research, and I assure you computability theory is not a subset of it.

No - complexity theory deals with the "hardness" of problems not of algorithms, and yes, then the bounds on what algorithms we can write to solve them.

By that metric (and even by your own argument "the inability for algorithms"), the undecidability of the halting problem definitely fits within the complexity definition.

If you won't listen to me (someone who does this for a living) maybe you will listen to a quote from wikipedia:

> imposing restrictions on the available resources is what distinguishes computational complexity from computability theory

And for the record when I say the ability of algorithms to do something I mean the class of all possible algorithms.

That is what I understood you as saying. I still don't see how my phrasing of the decidability of the halting problem as a complexity problem is any less valid.

In any case, it's clear from your appeal-to-wikipedia that this conversation is over.

> I still don't see how my phrasing of the decidability of the halting problem as a complexity problem is any less valid.

Because you are not constraining any resources.

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).

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.

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.

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.

IPC boundaries, interface size, basic block count and CFG arity, number of different storage classes, number of different objects, number of different object lifecycles, &c.

I'm not saying there's one best known way to measure the complexity of a system, just that it is measurable.

These are black box metrics, better then counting lines of code, but essentially never truly able to describe the complexity of a system. To my knowledge, there's not even a strict theoretical definition describing what complexity is.

This seems like a discussion that ends in us arguing about the validity of the concept of a human soul.

>This seems like a discussion that ends in us arguing about the validity of the concept of a human soul.

I disagree. There is a logical end, so long as either of us have the capability of admitting we're wrong.

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.

>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).

My point was that different designs can be more or can be less scalable; poor designs require you to change lots of things to make one functionally-distinct change. There was no "it" (specific class of architectures) I was calling O(n^2), but an example case might be where all the interfaces assumed p fields, each with q bytes, then having one component pass more information would require updates to all components O(n) rather than just that one.

I don't see how describing an O(n log n) system sheds further light on any of this.

Reply on news.ycombinator.com