Efficient code is one of the most important parts of software development, in fact the only thing more important than this is planning and testing. How efficient your code is determines how fast your application will run - and it is this that will have a lasting impression on your users. If the application takes ages to do anything then your users will quickly get fed up with it and ditch it in favour of software that works better. The best time to make the most of your code is during planning - by calculating the efficiency of functions you can calculate which option will be best by comparing the "Big Oh" notation for them.
"Big Oh" notation (also known as Bachmanna-Landau notation) refers to the "order" or complexity of the function. This idea is a method which allows us to calculate the complexity of a function as something that is quantifiable and without taking into account system resources. The concept of this notation was originally developed purely for the mathematical purpose of dealing with infinitesimal numbers but has since become a tool by which software engineers can calculate the "cost" of proposed functions based on pseudo-code before actually writing any code.
Before going in to any detail let us consider a basic function -this should aid in explaining how the notation works.
function test_function ($x)
{
echo 'forwards';
for ($i = 0; $i < $x; $i++) {
echo $i;
}
echo 'backwards';
for ($i = $x; $i > 0; $i--) {
echo $i;
}
}It's a very simple function, and it doesn't really do anything useful other than to serve the purpose of being an example. This function's complexity would be noted as being O(n) - it may not yet be clear how I've come to that conclusion, but please wait whilst I explain.
This can be calculated by determining how "long" it will take to perform this function in a series of steps. So let's start with echo 'forwards' - this will always take the same amount of time so can be represented as a constant, as can echo 'backwards' so that leaves us with two for loops. Each loop will go through n iterations, each time echoing the current step, so each loop runs will have a complexity of n. So from this we can calculate an asymptotic expansion Σ2n + x where x is an arbitrary constant and n tends towards infinity. My method of notation here isn't 100% perfect as it's not easy to correctly represent this on a computer, but normally we would see a value for n = 1 below the sigma and infinity above the sigma.
When we refer to the complexity of a function though, we reduce it to it's most significant component ignoring any constants and terms of a lower order. So, in the case of the above example we would have a linear order reliant on n, which is O(n). It doesn't matter how comples the expansion is either, if we had calculated a function as having a time complexity of 2n2 + 5n + 6
we would only represent it as (n2). The reason for this is the size; when n is sufficiently large we will reach the point where 5n and 6 are negligible - it is n2 that sets the trend of the value.
We aim for more efficient algorithms to reduce the "cost" of running it - this is measured in terms of processing time, space, or any other resource required. A rough scale of how algorithms differ is as follows:
log n < n < np < pn < n!The scale is based upon n being sufficiently large as it tends towards infinity - so from a certain point of view you can say that this is a good indicator to how an algorithm might scale for heavier usage. In this scale an algorithm of cost n factorial would potentially be a very expensive algorithm to run, whereas on the other end of the scale a logarithmic algorithm would be far more efficient. So where we've seen a loop that runs for n times would have O(n) we can also see that other operations such as assignments count as O(1) as they have constant time. Such an example might be:
var some_variable = '1';This is only run once and will have a running time dependant on the machine's computational power, when we note this as an order of complexity we say it is asymptotic.
Let us consider another example which is PHP code, though could also have been in pseudo code:
function example2 ($n)
{
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $i; $j++) {
echo 'something';
}
}
}
At first glance you can instinctly tell that it is a more complex example than our previous one. The main difference here is that the loop inside the loop will be run n times, and the inner loop on each iteration will be run n - 1 times. So this means we can calculate that the echo statement will actually be executed (n * (n - 1) / 2) times. If we resolve this equation to it's simplest form we have (n2 - n) / 2. This would therefore equate to a complexity of O(n2) and so we can see this has a higher time complexity than the first example and so would be a more expensive algorithm to run.
