12 ms·

Brushing up on Computer Science Part 1, Big O

83 points by messel 16y ago

Montagist 16y 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 16y ago
  More or less strict definition of O() requires limits first which isn't exactly an easy topic in high school.
summitpush 16y ago
The link to the "Plain English Explanation of Big O" is the best part of this article.
- messel 16y 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.
bane 16y ago
Next up? Big-Omega and little-o. http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachma... http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation 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_s 16y 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 16y 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.
  - anamax 16y 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.
    - scott_s 16y ago
      I think you mean plumbing in the sense of connecting already existed components. I'll grant that. But would you consider someone who can only do that a fantastic developer? And, yes, I know we're discussing almost pure semantics.
      - anamax 16y ago
        > But would you consider someone who can only do that a fantastic developer? In some circumstances yes, in others, no. We don't expect medical doctors to be good at everything, we don't expect jet engine mechanics to understand diesels, and so on, so why would we judge software folk based on some universal standard? Let's look at it from the other side. If someone isn't very good at plumbing (or floating point, or crypto, etc), does mean that said someone is not a fantastic developer?
shortlived 16y 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 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/handouts/23-section-3.pdf http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/... (see last page) and answers: http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/handouts/23a-section-3-solutions.pdf http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/... I also recommend the algorithms course from ArsDigita, http://aduni.org/courses/algorithms/ http://aduni.org/courses/algorithms/
Homunculiheaded 16y 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&tid=11866 http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&#38...
- ominous_prime 16y 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 16y 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

83 points by messel 16y 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 16y ago
More or less strict definition of O() requires limits first which isn't exactly an easy topic in high school.

summitpush 16y ago

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

messel 16y 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.

bane 16y ago

Next up? Big-Omega and little-o. http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachma... http://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation 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_s 16y 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 16y 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.
- anamax 16y 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.
  - scott_s 16y ago
    I think you mean plumbing in the sense of connecting already existed components. I'll grant that. But would you consider someone who can only do that a fantastic developer? And, yes, I know we're discussing almost pure semantics.
    - anamax 16y ago
      > But would you consider someone who can only do that a fantastic developer? In some circumstances yes, in others, no. We don't expect medical doctors to be good at everything, we don't expect jet engine mechanics to understand diesels, and so on, so why would we judge software folk based on some universal standard? Let's look at it from the other side. If someone isn't very good at plumbing (or floating point, or crypto, etc), does mean that said someone is not a fantastic developer?

shortlived 16y 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 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/handouts/23-section-3.pdf http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/... (see last page) and answers: http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/handouts/23a-section-3-solutions.pdf http://www-cs-faculty.stanford.edu/~eroberts/courses/cs106b/... I also recommend the algorithms course from ArsDigita, http://aduni.org/courses/algorithms/ http://aduni.org/courses/algorithms/

Homunculiheaded 16y 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&tid=11866 http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&#38...

ominous_prime 16y 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 16y 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