## Introduction

Big-O notation (pronounced 'Big Oh') is used in computer science as a means to describe the worst-case performance of an algorithm. It's one of the things you really should learn if you're interested at all in designing efficient algorithms.The formal definition is as follows:

This definition is a very format way of saying that Big O-notation is the upper-bound/worst-case of a function.f(n) = O(g(n))meansc*g(n)is an upper bound onf(n). Thus there exists some constantcsuch thatf(n)is always≤ c*g(n), for large enoughn(i.e. ,n ≥ nfor some constant_{0}n)._{0}

The Algorithm Design Manual, Steven S. Skiena

## Worst-case

Big-O notation has a counterpart Ω-notation (Big Omega notation), which describes the best-case instead of the worst-case. While it may seem unintuitive, this is actually much less useful when analysing performance issues. In general we care much more about the worst-case performance as we want everything to run as smooth as possible, not randomly fast and randomly slow. Consider the following function:public Boolean DoesTextContainChar(String text, char character) { for (int i = 0; i < text.length(); i++) { if (text.charAt(i) == character) { return true; } } return false; }If we run this function when

`text`

is very small or when `character`

is near the beginning of `text`

then it will run very quickly. But what about when `text`

is extremely long and `character`

doesn't exist? This is the worst-case of the algorithm.## Simplicity

Big-O notation ignores the details of an algorithm and focuses only on the largest power in the term. A precise analysis of an algorithm could look something like this:*f(n) = 3n*

^{3}+ 60n^{2}+ 8n + 103The beauty of Big-O notation is that we can ignore most of this and just focus on the largest term. We can even ignore the constant, consider the same algorithm written in a low-level language runs 3 times faster than when written in a high-level language, it's a detail that isn't really important when looking at the algorithm itself. So the function above in Big-O notation is

*f(n) = O(n*

^{3})##
*
O(1)*

An *O(1)*function always runs in the same time regardless of the input size.

public Boolean IsCharCaps(char character) { int asciiCode = (int)character; return asciiCode >= 65 && asciiCode <= 90; }

##
*
O(log n)*

An *O(log n)*function grows at a rate of the logarithm (base 2) of the input size. A lot of sorted array search algorithms like the binary search algorithm are

*O(log n)*. This is only really possible when you can ignore input elements entirely.

public Boolean BinarySearch(int[] sortedArray, int value, int min, int max) { if (max < min) return false; else { int mid = (min + max) / 2; if (sortedArray[mid] > value) return BinarySearch(sortedArray, value, min, mid-1); else if (sortedArray[mid] < value) return BinarySearch(sortedArray, value, mid+1, max); else return true; } }

##
*
O(n)*

An *O(n)*function grows at the same rate as the input size.

public Boolean DoesTextContainChar(String text, char character) { for (int i = 0; i < text.length(); i++) { if (text.charAt(i) == character) { return true; } } return false; }

##
*
O(n*^{2})

An ^{2})

*O(n*function grows at a rate of input size to the power of 2.

^{2})public static int[] InsertionSort(int[] array) { for (int i = 1; i < array.length; i++) { int item = array[i]; int indexHole = i; while (indexHole > 0 && array[indexHole - 1] > item) { array[indexHole] = array[--indexHole]; } array[indexHole] = item; } return array; }More information on insertion sort can be found here.

##
*
O(2*^{n})

An ^{n})

*O(2*function's time doubles whenever the input grows. If your function is

^{n})*O(2*it's going to really struggle when the size of your input data increases even a little. Writing one would make me feel a little icky.

^{n})