Understanding Big O Notation with Python Examples
In the world of software development and computer science, performance is everything. When you’re designing an algorithm, one of the key considerations is how efficiently it handles increasing amounts of data. This is where Big O notation comes into play. Big O provides a mathematical framework to describe the efficiency of an algorithm in terms of time or space as a function of the size of the input.
Get DeVillar | Renata Villar’s stories in your inbox
Join Medium for free to get updates from this writer.
In this post, we’ll explore some of the most common types of Big O notations — O(n²), O(n), O(2^n), O(n log n) and O(n!) — and what they mean for the performance of your algorithms.
What Is Big O Notation?
Big O notation is a way to express the upper bound of an algorithm’s running time. It provides a worst-case scenario that helps developers understand how an algorithm behaves as the size of the input grows. Big O ignores constants and lower-order terms because they have less impact on the growth rate as the input size increases.
Why Is It Important?
Understanding Big O notation is crucial for optimizing your code, especially when dealing with large datasets. It helps you:
- Predict performance: Know how your algorithm will scale.
- Compare algorithms: Decide which algorithm is more efficient for your needs.
- Optimize code: Identify bottlenecks and make informed choices to improve performance.
Common Big O Notations
O(n²): Quadratic Time Complexity
O(n²) describes an algorithm whose performance is proportional to the square of the size of the input data. As the input size doubles, the running time quadruples. This is typical for algorithms that involve nested loops, where the outer loop runs n times and the inner loop also runs n times.
Example
Imagine you have a simple algorithm that checks all pairs in a list:
def check_pairs(lst):
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
if lst[i] == lst[j]:
return True
return FalseThis algorithm compares every element with every other element, leading to a time complexity of O(n²). For small datasets, this might not be an issue, but as the input size grows, the algorithm becomes significantly slower.
O(n): Linear Time Complexity
O(n) describes an algorithm whose running time increases linearly with the size of the input data. This is the most efficient time complexity you can achieve for algorithms that need to examine every element in the input data.
Example
Consider a simple search operation in a list:
def linear_search(lst, target):
for item in lst:
if item == target:
return True
return FalseHere, the algorithm goes through each element of the list once, making the time complexity O(n). As the input size grows, the running time increases linearly.
O(2^n): Exponential Time Complexity
O(2^n) describes an algorithm whose running time doubles with each additional element in the input. This is one of the least efficient time complexities and is often seen in algorithms that involve recursive branching, where each step can lead to multiple sub-problems.
Example
A classic example is the recursive solution to the Fibonacci sequence:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)This algorithm has an exponential time complexity of O(2^n) because it solves each sub-problem multiple times. For large values of n, this algorithm becomes impractical due to its extremely high running time.
O(n log n): Logarithmic-Linear Time Complexity
O(n log n) is a time complexity that represents a balance between linear and logarithmic growth. It’s often associated with more efficient sorting algorithms, like Merge Sort and Quick Sort, which divide the problem into smaller sub-problems and then combine the results.
Example
Here’s a simple implementation of Merge Sort:
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
sorted_list = []
while left and right:
if left[0] <= right[0]:
sorted_list.append(left.pop(0))
else:
sorted_list.append(right.pop(0))
sorted_list.extend(left + right)
return sorted_listMerge Sort has a time complexity of O(n log n), making it significantly faster than O(n²) algorithms for large datasets. The log n factor comes from the algorithm dividing the problem in half with each recursive call, while the n factor comes from the need to merge all the sub-lists together.
O(n!): Factorial Time Complexity
O(n!) represents a factorial time complexity, where the running time grows factorially with the size of the input data. This is one of the most inefficient time complexities, often associated with algorithms that generate all possible permutations of an input set.
Example
A classic example of an O(n!) algorithm is one that generates all possible permutations of a list:
def permute(lst):
if len(lst) == 0:
return []
if len(lst) == 1:
return [lst]
permutations = []
for i in range(len(lst)):
m = lst[i]
rem_lst = lst[:i] + lst[i+1:]
for p in permute(rem_lst):
permutations.append([m] + p)
return permutationsFor an input list of size n, this algorithm generates n! permutations. For small input sizes, this might be feasible, but as n grows, the number of permutations increases dramatically, making the algorithm impractical for large datasets.
Conclusion
Understanding Big O notation is a critical skill for any developer or computer scientist. It allows you to evaluate the efficiency of your algorithms and make informed decisions about which approach to take when solving a problem.
- O(n²): Avoid for large datasets; typically results from nested loops.
- O(n): Efficient, scales linearly with the input size.
- O(2^n): Highly inefficient; usually indicates an algorithm with recursive branching.
- O(n log n): Efficient for sorting and other divide-and-conquer algorithms.
- O(n!): Extremely inefficient; avoid unless absolutely necessary, such as when generating all possible permutations.
By mastering Big O notation, you’ll be better equipped to write algorithms that not only work but scale efficiently as the size of the data grows.







