Title: Big-O Notation
Slug: big-o_notation
Summary: Using Python.
Date: 2016-05-01 12:00
Category: Algorithms
Tags: Basics
Authors: Chris Albon
Want to learn more? Check out Data Structures and Algorithms in Python
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:
Below are some examples of a few of these.
In [1]:
# Create a list 100 elements long
n = list(range(100))
In [2]:
# Create a function that, regardless of the length of n,
def constant(n):
# returns 1
return 'Number of operations: ' + str(1)
In [3]:
constant(n)
Out[3]:
In [4]:
# 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))
In [5]:
logarithmic(n)
Out[5]:
In [6]:
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))
In [7]:
linear(n)
Out[7]:
In [8]:
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))
In [9]:
quadratic(n)
Out[9]: