Big-O notation for software Developement

What is Big-O notation?

What is Big-O notation and why should developers know about it?

In computer science, Big-O notation is used to classify algorithms according to how much their run time or space requirements grow as the input size grows.

As developers we always want to write code that is highly efficient, therefore we should use Big-O notation to analyse and optimise our code. Analysing our code involves looking at code that is used to solve a particular problem and measuring its running time and resources across two metrics:

  1. Time Complexity: Here we ask, “How long will this code take to execute?”
  2. Space Complexity: Here we look at how much resources a specific function consumes as the input into the function changes/increases.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation. If we map the relationship between the inputs of a process and the time or space complexity, perhaps by plotting that series, we might find that there is a general trend line or relationship between increasing inputs ( on the x-axis ) and increasing time or resources for execution ( on the y-axis ).

Essential Math for Software Development: The Quadratic Function ‘O(n^2)’

When analysing the performance of a algorithm a developer should avoid having a time and space complexity that resembles various quadratic functions as a graphed below:




Quadratic functions. Taken from http://mathonweb.com/help_ebook/html/functions_4.htm 

These are functions of the form:

y = a x^2 + b x + c

Where a, b and c are constants. Their graphs are called parabolas. This is the next simplest type of function after the linear function. Falling objects move along parabolic paths. Quadratic functions are described in detail here.

In this model, the relationship between increasing inputs and the time or resources consumed for a specific function resembles a sharp curve upwards. In this context, it can be said that input quadratically affects the running time or resources used by our algorithm. A common example of this is in nested loops.

for (int i = 0; i <n; i += c) {
    for (int j = 0; j < n; j += c) {
    // some O(1) expressions
    }
}

Linear vs Binary search algorithms

A linear search algorithm scans each individual item of our database, one item at a time, and uses the equality operator to see if the record currently being scanned matches our search criteria.

In a binary search, however, we cut down the number of inventories that needs to be scanned, each and every time we perform a check.  The nuIn a binary search, however, we cut down the number of records that needs to be scanned, each and every time we perform a check.  The number of records that needs to be scanned is halved each time a search is performed as binary search uses the greater than, equal and less than operation when scanning.  However, our database has to be o be sorted from smallest to largest in order for binary search to work, whereas this is not the case in a linear search algorithm.

A practical example of a linear search algorithm

Sequential or linear search checks each individual record in in our database for a match.

function linearSearch(arr, elToFind) {
  for (var i=0; i<arr.length; i++) {
    if (arr[i] == elToFind) {
      return i;
    }
  } return null;
}

linearSearch(rainbow, "green"); // returns 3
linearSearch(rainbow, "white"); // returns null

A practical example of a binary search algorithm

Whereas binary search accesses data randomly, linear search performs equality comparison. Binary search performs ordering comparisons with the operators less than, equals or greater than.

function binarySearch(sortedArray, elToFind) {
  var lowIndex = 0;
  var highIndex = sortedArray.length - 1;
  while (lowIndex <= highIndex) {
    var midIndex = Math.floor((lowIndex + highIndex) / 2);
    if (sortedArray[midIndex] == elToFind) {
      return midIndex;
    } else if (sortedArray[midIndex] < elToFind) {
      lowIndex = midIndex + 1;
    } else {
      highIndex = midIndex - 1;
    }
  } return null;
}

var sortedRainbow = ["blue", "green", "indigo", "orange", "red", "violet", "yellow"];
binarySearch(sortedRainbow, "green"); // returns 1
binarySearch(sortedRainbow, "white") // returns null

The World Famous “Fibonacci algorithm”

Let’s briefly unpack the Fibonacci algorithm, as expressed in the Big-O notation below:

T(n) = T(n-1) + T(n-2) + O(1)

If we momentarily ignored the space complexity when looking at the performance of the time complexity of the Fibonacci algorithm, as expressed above, we find that the time taken to complete the process will grow exponentially as the input into the function for the Fibonacci algorithm grows. Each time the input increases the growth of the function doubles.

function Fibonacci(n){
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

For those who are not familiar with this algorithm, a Fibonacci algorithm is a group of numbers where you can find the next number in a sequence by adding the two previous numbers in the sequence together.

If you are interested in Big-O notation, and its theoretical background, check out this video:

Conclusion

I would encourage you to think about how you can use best practise techniques to optimise your code. Can you think of practical scenarios where you can use Big O Notation? Are you happy with the performance of your software and what have you tried to do about it? Let me hear what you have to say in the comment section below.