Big O Notation

Big O Notation is essentially a measure of the performance/complexity of an algorithm, also known as the time complexity of an alogrithm.

There are 5 main notations: Constant, Linear, polynomial, Exponential and Logarithmic.

Constant has a time complexity of O(1). This means it has a constant execute time no matter the size of the input as the input does not affect the number of lines of code executed. These do not contain loops, recursions or calls to any other non-constant time function.

Linear has a time complexity of O(n). This means its execute time grows directly proportional to the size of the input, n.

Polynomial has a time complexity of O(n^x). This is similar to Linear but the execute time rises much steeper with increasing input size. Polynomial algorithms contain nested loops which increases x per nested loop.

Exponential has a time complexity of O(2^n). This is similar to polynomial but the execute time rises even more steeply with input size. Per input unit, the execute time doubles so these algorithms take a long time to run. This type of algorithm is often seen in brute force algorithms.

Logarithmic has a time complexity of O(log n). This is like the opposite of polynomial. The execute time decreases in steepness with increasing input size. This is often seen in divide and conquer algorithms.

Polynomial and exponential algorithms should be avoided if input size n is large as it will have a very inefficient and slow execute time. A logarithmic algorithm should instead be considered as its execute time scales very well with larger input sizes.

To calculate a big O of an algorithm you take the most significant term and remove the constants.

E.g: 3n^2 + 5n + 2. Has big O notation of n^2.