Big O notation basics for web developers

Today we discuss Big O notation. It is often said that Big O notation makes 'boring math' interesting. Does it? There's only one way to find out.

So, What in the world is Big O notation? The technical definition goes like this: Big O notation, also referred to as Landau's symbol, is a symbolism used in complexity theory, computer science and mathematics to describe the asymptotic behavior of functions.

Basically, it tells you how fast a function grows or declines.

Landau's symbol comes from the name of the German number theoretician Edmund Landau who invented the notation. The letter O is used because the rate of growth of a function is also called its Order.

The formal definition is: f(x) = O(g(x)). 

Here f(x) and g(x) are functions representing a relationship in which g(x) grows depending on f(x) given that f(x) never grows faster than g(x). 

By now, you must be asking yourself, what does Big O have to do with web development? Well, the answer lies in algorithms. Often, web developers are interested in the complexity of algorithms. Complexity in this context refers to the rate at which an algorithm's computational steps increase when the size of the input of the algorithm grows. The assessment is made using the worst case scenario; that is, if the input is as large as it can possibly be, how does the algorithm respond?

Here is a list of classes of functions that are commonly encountered when analyzing algorithms. The slower growing functions are listed first. c is an arbitrary constant:

figure 1 - common big O functions 

One of the fastest growing functions is the quadratic function - O(N^2). O(N^2) represents an algorithm whose complexity is directly proportional to the square of the size of the input data set; this means that complexity equivalent to size N x N is expected from an input of size N. This is common with algorithms that involve nested iterations over the data set. The snippet of code in figure 2 below illustrates a function that exemplifies quadratic behaviour:

figure 2 - quadratic behavior

To further illustrate the relationship between big O and web development, we will now look at two search algorithms and determine their complexity using big O notation. The two algorithms in question are linear search and binary search. Linear search looks through each and every item in a list without skipping any item. This yields a complexity of O(N) which according to figure 1, is linear. It is linear because there is a linear relationship between the number of iterations performed and the size of the list to be searched. Example code for a linear search algorithm is shown in figure 3 below: 

figure 3 - linear search

On the other hand, binary search starts halfway through a sorted list and determines which half of the list is greater or less than the value being searched for. This thus determines whether the value is in the first or second half of the list. The step is repeated for whichever half the value is most likely in until the value in question is located. This search sees a smaller rate of growth in the number of steps required to achieve it when the list to be searched grows. The Big O notation to denote binary search is thus O(log N) which, according to figure 1 above, displays logarithmic growth. Below is a javasctipt code snippet depicting a function that performs binary search: 

 figure 4 - binary search

According to figure 1, logarithmic algorithms are faster than linear ones and therefore the verdict is as such: binary search is faster than linear search OR linear search displays greater complexity than binary search.

The last example of Big O notation we are going to delve into involves the fibonacci sequence; and don't worry, this is not boring math. 

The fibonacci sequence was made famous by an Italian mathematician named Leonardo Bigollo Pisano. To get the next number in the sequence, one simply has to add the two numbers that preceed it in the sequence. For example, in the sequence 1, 1, 2, 3..., the first four numbers of the fibonacci sequence are depicted. To obtain the next number in the sequence, simply add the two preceeding numbers which are 2 and 3 to get 5 and so on. 

Below are two algorithms that determine the first five numbers of the fibonacci sequence and we are going to use the Big O to determine their complexity:

figure 5 - fibonacci by recursive function

figure 6 - fibonacci by for loop

In the first code example(figure 5), the algorithm employs a recursive function to determine the n-th number of the fibonacci sequence. Now, with this algorithm, the function has to call itself several times to determine each number in the sequence. The larger n is, the more times it has to call itself. In fact, the rate of growth of the number of steps is so great that it is exponential and thus O(C^N) - refer to figure 1 above. 

The second code example(figure 6) uses a for loop to determine the next number in the sequence. It simply accesses the last two numbers of the pre-established sequence and determines the next number. The number of iterations made by the for loop depends directly on the size of sequence required. Therefore, the rate of growth of computation steps is linearly related to the input which is the number of items in the sequence to be determined. Thus, the second code example is linear O(N) - see figure 1 above.

Therefore, according to the metric in figure 1, the second code example(figure 6) is a more efficient way to determine fibonacci numbers because its complexity is linear when compared to code example one in figure 5 whose complexity is exponential...