no. 15| 06.16.2014 |
Big O Notation.
O(n log(n)) what?
Whoa. Mathy.
Many thanks to Rob Bell for his blog post “A Beginner’s Guide to Big O Notation” . After doing some initial research on the topic — which is completely new to me — I slogged through a ton of very technical, math heavy, jargon filled explanations that made almost no sense to me whatsoever. I considered switching to a different topic, but then ran across Mr. Bell’s post.
In a nutshell, Big O is a way to express computational complexity with an equation. All the math heavy explanations made it hard for me to understand the point in the context of what we’re doing in DBC. But once I started to understand the basic concepts, I could see places where it might influence decisions I make about code structures. (Even though right now I don’t necessarily get all of the mathematical details.)
Big O Notation provides a way to describe and compare the computing resources required by any given operation or algorithm. It’s one thing to say “Checking a variable to see if it’s null or not is easy, but a linear search for an item in an array with 10 million elements is hard.” Big O Notation allows for more specificity.
Big O is concerned with “worst case” scenarios, and can help programmers watch out for places where a code technique won’t scale well. A loop that does some action on each element of an array is fine when the array is relatively small — but you could be in real trouble if your array gets huge for some reason. (Suddenly your app has a billion users? Lucky you! Now it’s broken because your ‘search_user_array’ loop takes 300 years to finish. Ooh and look! Your investors are mad.)
Rob Bell’s article is short, easy to understand and worth the read. I won’t recreate it here. The super quick boil down is that some computations will take the same amount of computing time and space (think RAM, or disk space) no matter what the size of the data set is. You can find out if the first element of something is null or not in the same amount of time, no matter how big the something is.
And computations that do require more resources as the input data set grows? They tend to fall into recognizable patterns. If you graph the computational needs against the size of the data set, you’ll see some that form a straight, upward sloping line, others will show variations of logarithmic or exponential curves — some gentle, some that start slow and then shoot up to near vertical.
Knowing what types of computations fall into which Big O “categories” (“Beginner’s Guide” has great code examples, and here’s a handy cheat sheet) helps programmers make decisions about the impacts and risks a particular algorithm could have when applied to a particular problem in it’s worst case form.