# Algorithm Concepts – Big (O) Notation

Big O notation helps us determine how complex an operation is. It provides information on how long an operation will take, based on the size of the data. It can also be used as a complexity measurement.

O comes from the Order of the function (growth rate), while n is the length of the data we work with.

Given the following formula:

f(n) = 8n5 – 3n4 + 6:

As n approaches infinity (for very large sets of data), 8n5 is the only one that actually matters, so all the lesser terms will simply drop. The constants drop as well, so the formula have a growth rate of O(n5).

The following table contain a list of the common O notations, from fastest (best) to slowest (worst).

### Time complexity

The running time describes how many operations an algorithm must do before it completes.

#### O(1)

For the following example, the growth rate is O(1), which means that the lookup is constant, no matter how big the container is.

#### O(n)

For the following example, the growth rate is O(n) because, for a vector with n=1000 (1000 elements), the number of operations will also be 1000.

#### O(n2)

For the following example, the growth rate is O(n2) because, for a vector with n=10 (10 elements), the number of operations will be 102.

• For each number i from 0 to 9 (Line 4)
• For each number j from 0 to 9 (Line 5)
• Display the values on screen ( [0][0], [0][1], …[9][9])

## Space complexity

The space complexity describes how much space must be allocated to run the algorithm.

For any algorithm, memory may be used for variables (constant, temporary variables), instruction, or execution.

Space Complexity is the sum of Auxiliary space and Input space.

Auxiliary space is the extra/temporary space that is used by the algorithm during its execution, whereas the Input space refer to the data received as input.

To calculate the space complexity, we need to know the memory required for the type of variables, which generally is different for different operating systems.

#### Constant

Let’s assume that the space requirement for an int is 4 bytes.

Variables a,b,c, and sum are integers, so they will take 4 bytes each => space requirement = 4*4 = 16. We add 4 more bytes to the return value => total is 20.

Because the space requirements is fixed, we call it to be constant.

#### Linear

In the above example, we receive a vector and we copy each element of that vector into a new one.

Therefore, assuming the size of an integer is 4 bytes, we will need 4*n bytes of space for the elements, where n is the size of the original vector.

The memory is linearly increased based on the size of the vector, so the space complexity is linear => O(n).