Brushing up on Computer Science Part 1, Big O

http://www.victusspiritus.com/2011/03/14/brushing-up-on-computer-science-part-1-big-o/

by messel • 15 years ago

83 27 15 years ago

Montagist• 15 years ago

Big-O...one of those things I never managed (or cared?) to pickup regardless of how many times it'd been drummed into me in school. Any article that explains it in an approachable way is fine by me.

adobriyan• 15 years ago

More or less strict definition of O() requires limits first which isn't exactly an easy topic in high school.

summitpush• 15 years ago

The link to the "Plain English Explanation of Big O" is the best part of this article.

messel• 15 years ago

I concur, and I'm the author. It's a wonderful introduction to Big O for folks that struggle with it. My post is merely a tool to help refresh my knowledge of fundamental concepts. William Shields does an excellent job of making Big O approachable to non-CS majors.

The only passage I take issue with is his description of O(n) arithmetic examples. In my thinking addition/multiplication are O(1) but I blame that view on years of thinking about FLOPs and letting thoughts of # of operations conflate with big O notation. In practicethe example of adding two large integers is a single operation, or at least a fixed size handful operations for arbitrary precision.

bane7• 15 years ago

Next up? Big-Omega and little-o.

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachma... http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notatio...

The information on wikipedia is hopelessly inadequate for the layman to learn from. I'd suggest somebody should edit it but it'd probably just get reverted.

Big-O is one of those concepts that is fantastically important for anyone doing algorithm design. I wouldn't go so far as to say that one has to master it, but thinking deep thoughts about the complexity of your algorithm can have amazing results.

This is one of those topics that, in my experience, few self-taught developers know about. A little story to illustrate. My wife was not really much into typical computer developer stuff (nerd things, programming for fun, playing with legos, etc.), but she was very strong in math and managed to work through a B.S. in C.S. During college she interned for a fantastic self-taught developer. I say fantastic because he managed to write a rock solid, very scalable e-commerce back-end for a very large and very active site. It was seriously impressive stuff.

Where he was struggling was with writing the reporting system. His system was gathering tremendous amounts of data, but aggregating and pooling that data into a meaningful and interactive reporting system had him completely lost. His best shot at it took somewhere between 11 to 12 hours to compile the results...or crash sometime during the night.

Eventually management wisely put the project on a backburner over other front-end tasks with a strong desire to revisit it soon. My wife was given the task to look at the code and see if she could do anything with it. After going through the code and experimenting for a few days, she discovered that the developer, in keeping things simple for himself was storing all of the data for aggregation in associative arrays (this was his convention and it actually really did make the code easy to maintain the way he used them). She dug into the associative arrays a bit and started calculating on a notepad the complexity of allocating millions of these things in memory. Very quickly she realized that there were two issues.

1) The associative arrays took a long time to allocate in memory, lots of bookkeeping variables and pointers were allocated with each one.

2) Each associative array ate up x bytes in memory. As they were allocated, in about 11 or 12 hours they would consume all available system memory, explaining the observed behavior.

So she set out, with a notepad to come up with a data structure and algorithm to do the task as optimally as possible and without consuming system memory.

Before ever writing any more code, she had come up with a solution. Then she went about rewriting a bunch of the system and it worked! In fact it was so fast that it could complete the task in about 30-45 seconds...meaning that it was feasible to make the process interactive rather than a nightly batch process.

When asked to explain how she arrived at the solution, my wife went into a discussion of Big-O and how she realized the old system showed growth that was far too fast to work, so she tried to set out and come up with a solution on a slower growth curve. Her developer boss had never heard of Big-O before, but the real-life example he had just seen blew him away.

He ended up learning the topic and applying it back to the rest of his work. A couple years later they spoke again and he said it was probably the single most important thing he had ever learned as it had opened up entire new projects for him that he thought were undoable as well as entirely new ways of analyzing data structured and algorithms that he had never considered.

scott_s7• 15 years ago

I'm having difficulty reconciling these two statements,

His best shot at it took somewhere between 11 to 12 hours to compile the results...or crash sometime during the night.

the developer, in keeping things simple for himself was storing all of the data for aggregation in associative arrays

With this one,

I say fantastic because he managed to write a rock solid, very scalable e-commerce back-end for a very large and very active site. It was seriously impressive stuff.

My reason is that I have difficulty calling someone a "fantastic developer" if they don't have a basic understanding of algorithms, data structures and systems. (If something takes a long time or crashes, run-away memory usage should be high on the list of suspects if you have basic systems knowledge.)

Nate75Sanders• 15 years ago

The problem he had other than the reporting may have already been ridiculously parallelizable.

If he wrote stable code and sharded user accounts or something, it might have worked with no real difficulties.

anamax2• 15 years ago

> My reason is that I have difficulty calling someone a "fantastic developer" if they don't have a basic understanding of algorithms, data structures and systems

A lot of development is plumbing.

bane7• 15 years ago

Yeah, I can understand why that might seem off. I'm using "fantastic" to mean "built really rock solid stuff, from scratch, on his own without any formal education". The e-commerce site, being a bunch of smallish transactions was much easier and more obvious to scale than a huge numbers crunch on a single system (this all predates the common usage of map-reduce algorithms which probably would have been an even better fit in the end).

Plus there's tons of great tech out there that helps with scaling a site (load balancers, sharding databases, etc.) that he didn't have to come up with, but not a lot for building custom reporting tools to spec for business types. Most of the requirements for the reporting tool weren't too bad -- "how many of this sku did we sell in the last 24 hrs, 7 days, 30 days, year, forever?" and could be solved pretty quickly and trivially. But scale something like that up, across all skus, correlated to individual users, or user locations, or supplier/warehouse availability, or whatever of another 100 variables and things get complicated very very fast, then aggregate those results and provide meaningful output to business types, and we're starting to talk Computer Science vs. Development.

The story wasn't mean to pump my wife up over her boss, at the end of the day, she solved one problem using her education, but she probably wouldn't be able to sit down and build what he built elsewhere. There's a tremendous amount of practical engineering knowledge that she (and I) just don't have (and don't learn in school) that her boss did have -- mostly things you just have to learn that kind of thing on the job.

I guess it really comes down to the semantics of developer. He's a great software engineer type, he can plug components together to build bewilderingly complex systems, but at the time he had a very naive view of algorithm design...which is a very different discipline.

amalcon• 15 years ago

It blew my mind the first time I read the proof that comparison sorts could never perform better than O(n log n) time worst or average-case.

It blew my mind the first time I realized that big-oh notation could be applied to any constrained resource (memory, disk I/O operations, bandwidth, everything) and not just CPU time.

It blew my mind when I realized that malloc and free, of all things, are not typically O(1) operations.

If you're doing anything even remotely interesting in computer programming, you'll benefit enormously from knowing about Big-O.

_delirium• 15 years ago

One problem with these kinds of articles on Wikipedia is that there's something of a deadlock between pedagogy-oriented and mathematical-precision-oriented editors. There's been a lot of discussion in WikiProject Mathematics over how to balance those concerns, in some cases producing multiple articles for the "introductory treatment" versus the "formal treatment", and in other cases just being better about organization, inclusion of visual aids and examples, etc. I think there's been an improvement in a lot of the math articles over the past 2-3 years in that regard, but the focus has been on more of the "core math" articles, and the CS articles have lagged (one reason is that mathematicians, including some very prolific professors, seem more numerous and active in the Wikipedia community than computer scientists are).

In theory, Wikiversity and WikiBooks are supposed to do even more on the pedagogy/introduction/tutorials side, but those projects have never gotten the same level of participation as Wikipedia has.

bane7• 15 years ago

One thing that I'd argue about is that with many many topics on Wikipedia, you can start at the top, and via hyperlinks, more or less piece together a pretty good understanding of the topic. With the CS and mathematics ones? Not so much. It's just dense layer upon dense layer of very raw mathematics.

There's an ongoing argument over why certain editors seem to want to constrain and duplicate the constraints of physical encyclopedias in a near infinite digital medium. But I do have to agree that tutorials and step-by-step instructions probably don't belong there.

But I'll be honest, when I have to look something like this up, I usually just go back to my old textbooks vs. wikipedia since the explanations are usually better presented. The section on big-O in WP is one of the better ones, but I'll be damned if I can figure out the walls of equations in some of the other articles. Most of the material doesn't appear in any textbook I've ever seen (perhaps that's saying something about the quality of the textbooks I used way back in College?)

shortlived• 15 years ago

For those looking to actually practice calculating Big O for functions, here are some useful problem sets, with answers:

http://www.cs.wustl.edu/~sg/CSE241_SP08/hw.html

Problem set for Big O and recursion:

http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/... (see last page)

and answers:

http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/...

I also recommend the algorithms course from ArsDigita,

http://aduni.org/courses/algorithms/

Homunculiheaded• 15 years ago

Personally, I think everyone who writes code for fun or profit should have a copy of the CLRS[0] nearby. The first few chapters are enough of have an excellent understanding of the topic of Big O. I would not recommend reading the book cover to cover, but each chapter is pretty self contained and after you get used to reading the book, makes for great weekend reading.

The thing with algorithms is you don't always see how they are useful if you aren't familiar with them, being able to quickly identify a hard problem as hard and have a solution already available is very valuable (even if you have to research the solution). If you code for fun, these are the funnest problems to think about. If you code for profit, even if you almost never need to use sophisticated algorithms in real software, making use of them even just once should give you a pretty good advantage over your competitors (since truth be told, outside of Google and the like most software developers do not have a copy of CLRS on their desk)

[0] http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&...

ominous_prime• 15 years ago

That's one of the few hard-copy books I keep around (I don't like wasting dead trees for something that will be outdated in a few years). I don't think it makes for a good self-teaching book for many people, because it's very long and dry, though it's still a great reference.

HenryR• 15 years ago

Nowhere does this article provide a definition for big-O notation. Also some important details seem to be missed - in particular the fact that O(f(n)) describes an asymptotic _upper bound_ on f(n). For example, searching on an unsorted array is O(n!), it's just not a very tight bound.

The linked-through article is much better.

edit: more precise wording

Brushing up on Computer Science Part 1, Big O

Related Stories