Brushing up on Computer Science Part 1, Big O

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

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/

The linked-through article is much better.

edit: more precise wording

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.