If you are a web developer or a programmer in general, you have most likely written algorithms for various tasks. [...] One specification of an algorithm is its correctness. You will probably assume that your algorithm works after testing it out a few times. However, if you can mathematically prove that your algorithm will work as expected for every input value possible, this is a huge bonus. I will not go further in to that subject in this writing. Another specification is its efficiency: how does the computing time relate to the amount of input? Is it a linear relation? Does computing time rise exponentially for the doubling of input? That's what this article will be about.

He starts by talking about the concept of "time complexity" and how it relates to the overall efficiency of the algorithm. He then gets into the definition and examples of Big O notation, including code showing O(n) and O(n^{2}) methods. He talks some about inefficient and efficient algorithms and follows with a refactoring example of moving from one to the other.

I'd like to share a topic today which was re-introduced to me by a lightningtalk of a colleague of mine. His talk was on the "big O notation". The big O notation is a tool you can use to express the order of complexity of an algorithm. It is useful because it lets you express the order of complexity of an algorithm without taking a lot of time profiling or researching the underlying algorithm. In other words: it gives you a quick way to gain an understanding of what might be wrong (or right) with a specific algorithm.

He introduces the notation as the result of a series of steps needed to solve a problem (ex. 2+2 is less complex than 2+2+2). He illustrates with PHP examples that show adding complexity to a class, adding sets of numbers, looping to find needles in haystacks and finding duplicates in an array of strings. Each of these expand on the theory and show more complexity as the article progresses.

]]>