# Big O Notation

Big O deals with classification of algorithms.

It does not help determine whether one algorithm is faster than another in a given classification.

Because it deals with classification, constants and non-determinate terms are dropped.

Example: an algorithm of O(n^2 + n) is considered O(n^2). Because, the growth rate is determine by the n^2.

Example: an algorithm of O(2n) becomes O(n). Because the growth is determined by n, not the constant 2.

Big O categories, from fastest growth rate (bad) to slowest growth rate(good):

O(n!)

ex: Listing all permutations of an array

O(2^n)

ex: Recursive Fibonacci

O(n^2)

ex: Bubble Sort, Insertion Sort

O(n log(n))

ex: Merge Sort

O(n)

ex: iterating over an array

O(log(n))

ex: Binary search on sorted array

O(1)

ex: Accessing an array element

Generally, if an algorithm has two loops that are not nested, the runtimes are added together. Example:

The runtime of the above would be O(m + n), where m is the size of arr1 and n is the size of arr2. But this can be simplified to just O(n) if we consider n to be the total number of elements in both m and n.

Generally, two nested loops are O(n^2)

The runtime of the above would be O(n^2).

However, not all nested loops have a runtime of O(n^2), as in the examples below:

Example1: (from A Common-Sense Guide to Data Structures and Algorithms, Second Edition )

In the above example the runtime is O(n). This is because the loops are iterating over different things. The outer loop is looping over the inner arrays. The inner loop is iterating over each inner array's numbers. Here each item of an array is only operated on once. So the growth is O(n).

This is in contrast to the previous example, where there was one array and each item in that array was looped over n times (where n is the size of the array).

Example 2:

In the above example the runtime is O(A * B). Here, each element of the B array is operated on by every element of array A. So the runtime is the length of array A * the length of array B.

Last updated