Learn about Big O Notation in PHP

In the coming articles, we’ll be looking at various algorithms and data structures. In order to better understand some of the terms and analysis of these we need to look at a topic called the Big O notation.

Big O for short, is a way that computer scientists gauge the relative speed of an algorithm or programming script. This is done by measuring a program in relation to its input size. This might seem a bit confusing at first, but once we get into it will start to make sense. You might also see this referred to as the time complexity of a problem.

Determining Big O
The Big O runtime on an algorithm is the time it takes for the algorithm to run in relation to its input. Particularly, we’re interested in what happens as that input grows larger. Lets, take a look at a simple example script.

$n = 100;

for($x = 0; x < $n; x++)
{
	echo($x);
}

The above script as you can see will simply iterate through each number from 0 to the value of $n and print it to the screen. In the case above, the script will execute 100 times and exit. However, what if we make the following change:

$n = 10000;

for($x = 0; x < $n; x++)
{
	echo($x);
}

Now, we can get it to run through the loop 10000 times. If we were to set $n even higher, we would see the amount of iterations increase at the same pace.

As we can see, the amount of time the script takes to run is directly influenced by the size of the variable. Being even more specific, we can say that the time increases at the same rate as our variable; for every one value we add to $n the loop will execute exactly one more time. This is known as linear time, and can be expressed in big O as O(n). The time the execution takes increases at a constant pace as n increases.

Looking at this from a time perspective, a linear time algorithm is likely to fast enough for most applications.

Now, let’s take a look at a bit harder of an example.

$n =3;
$j = 3;

for($x =0 ; <$n; x++)
{
	echo($x);
	for($y=0;$y<j;$y++)
	{
		echo($y);
	}
}

Now, this example is a little different since we have two loops. We know from our first example that each loop has a runtime of O(n). The way we handle this is simply to multiply them together; n * n which of course equals n². So this leaves us with a runtime of O(n²). This makes sense since for every pass through the first loop you have to it run completely through the second loop.

It doesn’t stop at O(n²), it’s perfectly acceptable to have O(n³), or really any number; we can express this as O(n^k) where K is any positive integer. This group can be collectively referred to as quadratic time.

Generally speaking, algorithms written in this speed are “fast” enough. They do grow much more quickly in linear time, but slow enough to still be of use. This is more true the lower the value of K. Most sorting problems we’ll look at later in worst case are quadratic time.

Now let’s look at another example. This is going to seem very trivial, but it’s an important step to understanding more complex problems. We’ve actually seen it in both other problems but have ignored it for now.

$x =1;

What’s the big O for this? Here, we have an example of constant time. If we were to put a loop after this that went to 10¹⁰ it wouldn’t matter, this assignment would still take the same amount of time. We model constant time with:

O(1)

In most cases you can ignore constant time, since the other part of the program grows much more quickly. Let’s take a look at something like that now.

$n = 1000;

for($x = 0; x < $n; x++)
{
	echo($x);
}

for($x =0 ; <$n; x++)
{
	echo($x);
	for($y=0;$y<j;$y++)
	{
		echo($y);
	}
}

Here, we have a mix of all three problems, what would be the big O of this? Well, looking back at our examples we might have something like:

O(1) + O(n) + O(n2) = O(n2)

Hold on a second, how were we able to eliminate ⅔ of the equation? This brings us to another point of big O; we are only really concerned with what happens as n gets really big. If you’ve ever studied limits this is vaguely similar, we are only really concerned what happens as the function grows towards the limit, which in our case is infinity.

Keeping that in mind, plug in 100,000 for each N and you’ll see by far the largest of the values comes from the quadratic, therefore its okay for us to eliminate the rest since their effect is negligible. This is the reason we are able to eliminate constant time operations from almost every algorithm or script we’ll look at.

Other Complexity Classes
These aren’t the only class of Big O. We’ll briefly touch on these for now, but we won’t go in depth until later on. The other common ones you’ll see are:

O(log(n)) – Logarithmic algorithms typically half the search space on each iteration. A good example of this is a binary search.

O(n^k) – exponential time – These are generally very slow, they increase to some constant k

O(n!) – Factorial time – These grow extremely fast. Listing all of the permutations of an array is factorial time.

These are important to know, but we won’t need them until a little later. We’ll dive more in depth with each one as they come up.

Congratulations! You’ve finished the intro for big O notation. Now, you have the primer necessary to really dive into looking at algorithms, and understand why some are better than others. We’ll be looking at many different algorithms and other implementations of Big O in the future articles, and you can apply the knowledge you learned here.