In computer science, Big O notation (also known as Time/Space Complexity) is used to “classify algorithms by how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large.” In other words, Big O is a measure to indicate how efficiently an algorithm performs in its worse case as the data it processes grows. An algorithm that performs well (i.e. quickly, with minimal space requirements) under one set of conditions may perform differently (i.e. worse) under a different set of conditions. Big O attempts to quantify that difference.

That’s all well and good from a theoretical standpoint, but I wondered how this was actually useful in the daily life of a coder. At the outset, my guess was that, while Big O is theoretical, optimizing a program for Big O would be useful when dealing with issues of scale. Like, for example, when a program initially designed to index and search one public library’s worth of books now needs to do the same for every public library in the state. Here are some other practical reasons for thinking about Big O when coding that I found:

• Understanding Big O can help you choose which type of data structure and sort algorithm are useful for your current problem.

• Writing good programs requires a solid understanding of tradeoffs in design. For example, in one scenario you may be able to afford to take up more memory in exchange for a faster run time. Sometimes you need to take up less memory, and must sacrifice run time to do.

• If nothing else, Big O is a common language programmers speak. You may never have to actually quantify Big O, but understanding it will facilitate the exchange of information and improve communication from programmer to programmer.

• If you have to manipulate a lot of data in memory, it behooves you to optimize your programs to handle the amounts of information you are dealing with in the most efficient way. Optimizing Big O will save you and your users time, which also of course means saving money.

Sources

http://www.perlmonks.org/?node_id=573138 http://stackoverflow.com/questions/1996457/what-is-the-big-deal-about-big-o-notation-in-computer-science http://www.perlmonks.org/?node_id=227909 http://www.perlmonks.org/?node_id=573208