# 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(n2)
• O(n3)
• O(2n)

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'


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'