Big O

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(n2)
cubic O(n3)
exponential O(2n)

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).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License