Friday, March 15, 2019

Big O Notation (Beginner's Guide)

Big O notation is used to represent of  the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.



Hopefully this article will help you gain an understanding of the basics of Big O and Logarithms.

 
O(1) - Constant time complexity
O(1) describes an algorithm that will always execute in the same time regardless of the size of the input data set.

bool isFirstNumberEqualToOne(List<Integer> numbers) {
  return numbers.get(0) == 1;
}
 
 
O(n) - Linear time complexity
O(n) describes the complexity of an algorithm that increases linearly and in direct proportion to the number of inputs. This is a good example of how Big O Notation describes the worst case scenario as the function could return the true after reading the first element or false after reading all n elements.

bool ContainsValue(List<string> elements, string value)
{
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}
 
 O(n2) - Quadratic time complexity
O(n2) represents an algorithm whose performance is directly proportional to the square of the size of the input data set. Adding more nested iterations through the input will increase the complexity which could then represent O(n3) with 3 total iterations and O(n4) with 4 total iterations.

bool ContainsDuplicates(List<string> elements)
{
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}
 
 O(2n) 
O(2n) represents a function whose performance doubles for every element in the input. This example is the recursive calculation of Fibonacci numbers. The function falls under O(2n) as the function recursively calls itself twice for each input number until the number is less than or equal to one.

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
 
O(log n) - Logarithmic time complexity 
O(log n) represents a function whose complexity increases logarithmic-ally as the input size increases. This makes O(log n) functions scale very well so that the handling of larger inputs is much less likely to cause performance problems. 
 
The example O(log n), Binary Search is a technique used to search sorted data sets. It works by selecting the middle element of the data set, essentially the median, and compares it against a target value. If the values match it will return success. If the target value is higher than the value of the probe element it will take the upper half of the data set and perform the same operation against it. Likewise, if the target value is lower than the value of the probe element it will perform the operation against the lower half. It will continue to halve the data set with each iteration until the value has been found or until it can no longer split the data set.
 
The example below uses a binary search to check if the input list contains a certain number. In simple terms, it splits the list in two on each iteration until the number is found or the last element is read. This method has the same functionality as the O(n) example — although the implementation is completely different and more difficult to understand. But, this is rewarded with a much better performance with larger inputs (as seen in the table). The downside of this sort of implementation is that a Binary Search relies on the elements to already be in the correct order. This adds a bit of overhead performance wise if the elements need to be ordered before traversing through them.
There is much more to cover about Big O Notation but hopefully you now have a basic idea of what Big O Notation means and how that can translate into the code that you write.
 
bool containsNumber(List<Integer> numbers, int comparisonNumber) {
  int low = 0;
  int high = numbers.size() - 1;
  while (low <= high) {
    int middle = low + (high - low) / 2;
    if (comparisonNumber < numbers.get(middle)) {
      high = middle - 1;
    } else if (comparisonNumber > numbers.get(middle)) {
      low = middle + 1;
    } else {
      return true;
    }
  }
  return false;
}
 
 
 




Graph showing how the number of operations 
increases with complexity
 
 
 
 
Other Topics:
 
at No comments:
Subscribe to: Posts (Atom)