## What is Big O

Big O notation provides a quantitative way of describing the run time or space efficiency of an algorithm.

## How It Works

Let's say that n is the number of elements to be processed in a given algorithm. In this algorithm, the number of comparisons, exchanges, data movements, and operations can be expressed as a function of n that we'll call T(n). The type of function that you get for T(n) will determine what Big O is. For example if n is a linear function, we say the algorithm is O(n). Here is a table with the different types of functions and their respective Big O description:

Function Type of T(n) | Big O description |
---|---|

constant | O(1) |

logarithmic | O(log n) |

linear | O(n) |

quadratic | O(n^{2}) |

cubic | O(n^{3}) |

exponential | O(2^{n}) |

## Examples

### Example 1

An algorithm that searches an unordered list of n elements for the largest value.

This would result in a run time of O(n) because n could need up to n comparisons and n reassignments. This gives us a funtion of T(n) = 2n. This is a linear function so run time is O(n).

### Example 2

An algorithm prints out the last five elements of an array.

This would result in a run time of O(1) because the algorithm will take the same amount of time regardless of the length of the array. Therefore T(n) = 5, which is constant. So O(1).