Philosophy

Complexity theory isn’t required to be a programmer

Complexity is sometimes portrayed as a corner stone to the theory of computation. What good would algorithm analysis be if we had no way to communicate our results? Theory has a role to play in our field, but I’m not sure it’s required on a typical day of programming. Perhaps I could even go as so far as saying you could be a good programmer without understanding much of anything about complexity theory.

My purpose in this article is not to question the value of complexity theory. It is a significant part of the theory of computer science and I even enjoy doing a bit of analysis sometimes. Here I’m just wondering out loud whether it actually plays a role in the day of a typical programmer.

Practical matters

The typical problems I see on projects are far removed from the realm of theory. We’re looking for concrete answers to specific problems we’re having right now. I need to know how to save a record in a DB, send a JSON request to the server, rotate an element on the screen, etc. While I might enjoy analysing an algorithm, the opportunity usually isn’t there.

Our process methods are tuned to producing functioning and maintainable code. My primary goal when writing a feature is not its theoretical efficiency, but it’s functional correctness. This means writing some tests, choosing an appropriate API, and putting in the correct runtime checks. Perhaps I need to get it peer reviewed before I merge to the main branch. Then I create a changelog and mark the issue as complete, or ready-for-testing.

On my typical day, week, or even month, I don’t even get close to computational complexity.

A day comes when I need to populate a collection of objects and pick some elements from it. Finally, it’s something that reminds me of the complexity theory I learned. I need this function to be efficient. I set about looking for solutions when a few realities dawn on me:

  1. I could probably solve the problem simply by creating a simple list, building a simple comparator, and then sorting the list. No analysis here; these standard library functions are efficient enough.
  2. I’m not even sure it needs to be efficient. I heard back from product management that our most extreme customer will only ever have a few thousand items in this. If I used a brain-dead brute force method it’s possible nobody would ever notice.

Minimal understanding

That’s all fine, but what if we really have a need to discuss algorithms? Say I’m doing a team presentation and I show that our O(n) solution is causing a problem. Bob gives me a funny look and asks, “What does O(n) mean?”.

I could stare at him blankly, unsure of why he doesn’t understand this stuff. I could just dismiss him, or I could even be mean and laugh at him. Or, I could simply answer, “It’s a measure of how long this code takes to run. Here n means the number of items in the container, and our algorithm does one comparison for each item in the container.” Bob answers, “ah, like a for loop that runs from 1 to n.” Good. Bob’s just grasped the basics of complexity theory.

Is that really all there is to it?

What is O(n)?

Here is where we might say common knowledge about complexity starts to waver significantly. Surely Bob doesn’t claim he understands the theory now, but how much do we ourselves really understand?

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. I’d need to make all sorts of assumptions before it had semblance of meaning. First off I need to know whether this is time or space complexity. 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.

The second major assumption is that I’m measuring some significant operation. O(n) must be referring to something in particular about the algorithm. For collections the convention seems to be the comparison operation, but is that really the best choice? In many practical situations it is the memory allocation that is costlier than comparison. For disk based algorithms the number of serializations could be the key cost. In some situations it may even be the cost of calculating a hash.

If we’re looking for fine details this hand-wavey approach is not so good. In theoretical analysis we can use the “random-access machine”. It’s a specific model of a computer for the purpose of analysis. How often do we state we’re using this machine while doing complexity analysis?

That aside, what does the value n in O(n) actually represent. In some cases it’s actually a measure of the number of steps, the time. But quite commonly big-O notation is actually measuring amortized time instead. If we’re dealing with hash maps we get even more lenient, allowing O(1) to mean the average expected time given a good hashing function.

Measurements

Does the big-O give us an idea of how an algorithm performs in practice? I wouldn’t allow somebody to replace an O(log N) algorithm with one of O(1) time complexity without first measuring it. Perhaps big-O isn’t even the right value here, often the non-simplified complexity is more revealing. Even with that, there are still a lot more details in practice.

How does the algorithm perform given the layers of caching in the CPU? I’m sure many of us have thought about this before, and even designed algorithms around this. I’m however still not aware of how to properly integrate this with complexity theory. I know there is cache-aware analysis, but the topic isn’t widely covered it seems.

How does the algorithm perform in concurrent computing? Clearly we’d prefer an algorithm that can scale over processors to one that can’t. We can even refer to scaling as having it’s own complexity, like having a linear gain over N processors. But again, I’m a bit uncertain of the precise way to do this. There is something called isoefficiency, but that topic also seems uncommon.

In practice I know that size complexity of data stores can easily dominate time complexity; it’s really costly to access large amounts of memory. I know that sequential reading is faster than random access. I know that alignment is good, but false sharing is bad.

Certainly there is a way to put this all together in theory, but I don’t know those details. This hasn’t prevented me from analysing such situations. Simply by reading about CPU architecture, and understanding threading, our colleague Bob could probably start doing the same type of analysis.

But to be honest, the situations where such details become vastly important are exceedingly rare in practical programming. It’s quite possible to be an effective programmer without understanding cache coherency.

Let’s be honest with ourselves

Algorithm analysis is an important field. The people that do this on a daily basis have a significant influence and value to our community. Our standard libraries, VMs, and operating systems are continually improved by this field of research. It’d be foolish not to recognize the value in this field.

It is however a speciality field. I don’t think one really needs complexity theory to be a programmer. I’m positive somebody could even become a really good programmer without ever seeing more than utmost basics. It’s far more important to understand the pitfalls of floating point calculations.

Knowing the theory can of course make one a better programmer. Just as knowing any number of details about computing will improve one’s abilities: cryptography, cache coherency, compiler design, functional programming, user experience, declarative programming, quality assurance and fault tolerance to name just a tiny few. There are an immense number of aspects to modern software. There’s no way we can be expected to know all of them, and certainly not to any level of expertise.

Complexity theory doesn’t stand out from this list. You can be a good programmer without knowing it.

I’ve been fortunate to work on a wide variety of projects, from engineering to media, from finance to games. Follow me on Twitter to share in my love of programming. If you’re interested in something special just let me know.

6 replies »

  1. I agree that Big-O is not the best way to rank algorithms. Most programmers believe that a O(1) algorithm is faster than O(N) algorithm when this is not the case. It only says that the performance of O(N) algorithms would deteriorate at a faster rate than O(1) algorithms as we increase the size of the data. At any given data size or even for small size changes, Big-O has nothing to say or compare about the performance of the algorithms. A O(1) algorithm with a large constant may be much slower than a O(N) algorithm with a small constant.

    But I still believe it is a nice concept to know. Something in the back of your mind to keep you from making bad choices. The problem is the misnomer that Big-O represents algorithm speed.

    With many programmers now working with cloud technologies and big data, I am of the opinion that Big-O would become more and more relevant.

  2. I use Asymptotic notations everyday. When I look at any piece of code or any problem, all I think about is how could it be done better if the analysis is already done. If the piece of code I am trying to copy from online, I stare at it to determine if it is actually doing efficient job. I understand that when you use the API calls most of the time, you never need to know about any of these. But in general I disagree that we don’t need to know about this. More over, if you have broad knowledge in lot of areas of computer science, each and every field has its own version of notation. Although we always use big O for time and space in general, when you take distributed computing, they consider rounds and message counts as major measure. So the notion is same. But the attributes considered are different and always mentioned in the algorithm/field. I see some points in the argument. But it is not convincing enough to say they are not widely used. If somebody happens to just make html webpages, probably they don’t need it. If you are writing codes that does any computation, the more theoretical knowledge you have, you have better insight about the performance of the code.

  3. I find that I use algorithmic complexity implicitly in lots of things I do every day. Every time I write to a database (relational or NoSQL) I ask myself how performance deteriorates. Every time I have a list of things, I ask myself how performance deteriorates as the list gets longer. Or when I add a database index. Plus, algorithmic complexity is not hard, as you said above, you can explain the gist of it in a few minutes and understand it pretty well in a week or so of thinking about it.

  4. Complexity theory usually means computational complexity theory, which is about proving things about complexity classes instead of algorithms.
    I think a better name would be “algorithm analysis”.

  5. Agree that it doesn’t matter that often when it’s big oh 1, log n, n… But every developer needs to recognize what happens when things go exponential relative to the prediction of the size of n for the given utility of an algorithm. When hiring I like to check that one can spot exponential time. I’m pretty terrible at exact big oh, but like you pointed out the details seldom matter.

  6. I think this is an interesting article, albeit, a little unclear. The first sentence refers to the theory of computation, then switches to day-to-day programming. The two are not the same thing. It’s like the difference between civil engineering and particle physics. In the end, I think that the amount of “algorithmic sophistication” required for a given programming task depends, as is always the case in life, on context.

    I thought I’d add a few of my own thoughts:

    1) It’s true that quite a lot of programming is fairly naive from an algorithmic point of view. Business programming often involves using some pre-packaged frameworks/APIs and then adding a layer of business logic in between. Said business logic may have a lot of rules that require some sophistication and subtelty to properly understand and translate into code, but they don’t need really clever algorithms. Or if the algorithms really are onerous, the amount of data is small enough that it doesn’t matter.

    2) Often enough we’d like to have a sophisticated algorithm to fundamentally reduce the complexity, but no one has figured it out. In such cases there’s often a patchwork of clever heuristics but the underlying engine is still brute force processing. Maybe chess is a simple example of this: The minimax algorithm is a brute force algorithm, but today’s programs do have a lot of clever tricks added to that basic framework to trim and prune the amount of processing needed. Big online services also do this. Let’s take an online store. They need to very quickly show product information from a large catalog. The basic idea is simply to use a map that takes up a huge amount of RAM, but there are levels of caching involved, and the map is presumably distributed across clusters of machines, etc. A lot of online services use this “huge amounts of RAM” approach, though I’m sure they’d love to do bettter to lower their data center costs.

    3) I agree that algorithms go beyond the naive idea that “big-Oh” is all that’s needed. I think that often enough college grads in computer science or related fields just take a few courses that involve algorithms from the 70s and 80s. That’s a fine starting point, but it may give people the wrong idea that that’s all there is. They enter the worlforce applying that thinking to everything even when that may not be the best approach, as the author has pointed out. When all you have is a hammer, everything looks like a nail.

    I am not knowledgeable enough to say for sure, but I imagine that sophisticated new paradigms in algorithm development do continue to be developed and used. It just depends on what kind of programming you’re doing.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s