Learning machine learning? Try my machine learning flashcards or Machine Learning with Python Cookbook.

# Big-O Notation

Big-O notation is used to classify the worst-case “speed” of an algorithm by looking at the order of magnitude of execution time.

From best to worst, some common Big-O’s are:

- O(1)
- O(log n)
- O(n)
- O(n log n)
- O(n
^{2}) - O(n
^{3}) - O(2
^{n})

Below are some examples of a few of these.

## Create Data

```
# Create a list 100 elements long
n = list(range(100))
```

## O(1) - Constant Time-Complexity

The length of `n`

has no bearing on the number of steps required to complete the function. This is the ideal.

```
# Create a function that, regardless of the length of n,
def constant(n):
# returns 1
return 'Number of operations: ' + str(1)
```

`constant(n)`

```
'Number of operations: 1'
```

## O(log n) - Logarithmic Time-Complexity

```
# Create a function that
def logarithmic(n):
# Creates a list of the operations performed
operations = []
# While n is longer than 1, repeat this:
while len(n) > 1:
# Find half the lengh of n
half_length = int(len(n)/2)
# Add half the values of n to operations
operations = operations + [n[0:half_length]]
# make n half the length of itself, then restart the loop
n = n[0:half_length]
# Return the number of operations
return 'Number of operations: ' + str(len(operations))
```

`logarithmic(n)`

```
'Number of operations: 6'
```

## O(n) - Linear Time-Complexity

```
def linear(n):
# Creates a list of the operations performed
operations = []
# For every item in n
for item in n:
# Add the item to operations
operations.append(item)
# Return the number of operations
return 'Number of operations: ' + str(len(operations))
```

`linear(n)`

```
'Number of operations: 100'
```

## O(n^{2}) - Quadratic Time-Complexity

```
def quadratic(n):
# Creates a list of the operations performed
operations = []
# For every item in n,
for i in n:
# Look at every item item in n
for j in n:
# and append it to operations
operations.append(j)
# Return the number of operations
return 'Number of operations: ' + str(len(operations))
```

`quadratic(n)`

```
'Number of operations: 10000'
```