- O(1): Constant time.
- O(log n): Logarithmic time.
- O(n): Linear time.
- O(n log n): Log-linear time.
- O(n^2): Quadratic time.
- O(n^3): Cubic time.
- O(2^n): Exponential time.
- O(n!): Factorial time.
- O(1): Constant space.
- O(n): Linear space.
- O(n^2): Quadratic space.
- Arrays
- Linked Lists
- Stacks
- Queues
- Hash Tables
TL;DR:
A very useful complexity chart by:
| Complexity | Description | Example |
|---|---|---|
| Constant Time | O(1) - Constant, regardless of input size | Accessing an array element by index |
| Logarithmic Time | O(log n) - Increases logarithmically with input size | Binary search |
| Linear Time | O(n) - Increases linearly with input size | Iterating through an array (no loops) |
| Linearithmic Time | O(n log n) - Linearly with input size * logarithmic factor | Merge sort |
| Quadratic Time | O(n²) - Increases quadratically with input size | Nested loops (2 loops) |
| Cubic Time | O(n³) - Increases cubically with input size | Triple nested loops (3 loops) |
| Exponential Time | O(2^n) - Increases exponentially with input size | Naive recursive Fibonacci |
| Factorial Time | O(n!) - Increases factorially with input size | Generating all possible permutations |
Time Complexity:
O(1): Constant time.
- No matter how large the input, the algorithm will always take the same amount of time to complete.
- Example: Accessing an element in an array by index.
def get_first(my_list): return my_list[0]
O(log n): Logarithmic time.
- The input size has a logarithmic effect on the running time of the algorithm.
- Example: Binary search.
# Binary search
O(n): Linear time.
- The input size has a linear effect on the running time of the algorithm.
- Example: Iterating through an array.
# Iterating through an array def print_all_elements(my_list): for element in my_list: print(element)
O(n log n): Log-linear time.
- The input size has a log-linear effect on the running time of the algorithm.
- Example: Merge sort.
# Merge sort
O(n^2): Quadratic time.
- The input size has a quadratic effect on the running time of the algorithm.
- Example: 2 nested for loops.
# 2 nested for loops def print_all_possible_ordered_pairs(my_list): for first_item in my_list: # O(n) for second_item in my_list: # O(n) print(first_item, second_item)
O(n^3): Cubic time.
- The input size has a cubic effect on the running time of the algorithm.
- Example: Iterating through a 3D array, or 3 nested for loops.
# 3 nested for loops -- Also use as last resort for 3D arrays def naive_matrix_mult(A, B): rows_A, cols_A = len(A), len(A[0]) rows_B, cols_B = len(B), len(B[0]) if cols_A != rows_B: raise ValueError("Matrices cannot be multiplied.") C = [[0 for _ in range(cols_B)] for _ in range(rows_A)] for i in range(rows_A): for j in range(cols_B): for k in range(cols_A): C[i][j] += A[i][k] * B[k][j]
O(2^n): Exponential time.
- The input size has an exponential effect on the running time of the algorithm.
- Example: Iterating through all subsets of a set.
# Iterating through all subsets of a set def print_all_subsets(my_set): all_subsets = [[]] for element in my_set: for subset in all_subsets: all_subsets = all_subsets + [list(subset) + [element]] return all_subsets # or def naive_fibonacci(n): if n 1: return n return naive_fibonacci(n - 1) + naive_fibonacci(n - 2)
O(n!): Factorial time.
- The input size has a factorial effect on the running time of the algorithm.
- Example: Iterating through all permutations of a set.
# Iterating through all permutations of a set def generate_permutations(arr, start=0): if start == len(arr) - 1: print(arr) for i in range(start, len(arr)): arr[start], arr[i] = arr[i], arr[start] # Recurse generate_permutations(arr, start + 1) arr[start], arr[i] = arr[i], arr[start]
Space Complexity:
O(1): Constant space.
- The algorithm uses a constant amount of memory, regardless of the input size .
- Example: Iterating through an array .
def print_all_elements(my_list): for element in my_list: print(element)
O(n): Linear space.
- The algorithm uses linear amount of memory, proportional to the input size .
- Example: Iterating through an array and storing the values in a hash table .
# O(n) space - Storing all elements in a hash table def reverse_list(arr): reversed_arr = [] for i in range(len(arr) - 1, -1, -1): reversed_arr.append(arr[i]) return reversed_arr
O(n^2): Quadratic space.
- The algorithm uses quadratic amount of memory, proportional to the input size .
- Example: Iterating through an array and storing the values in a 2D array .
# O(n^2) space - Storing all elements in a 2D array def create_identity_matrix(n): identity = [[0 for _ in range(n)] for _ in range(n)] for i in range(n): identity[i][i] = 1 return identity
O(2^n): Exponential space.
- The algorithm uses exponential amount of memory, proportional to the input size .
- Example: Iterating through all subsets of a set.
# Exponential Space - O(2^n) def power_set(arr): result = [[]] for item in arr: result += [subset + [item] for subset in result] return result
Common Data Structures:
Array
- Time Complexity:
- Access: O(1)
- Search: O(n)
- Insertion: O(n)
- Deletion: O(n)
Linked List
- Time Complexity:
- Access: O(n)
- Search: O(n)
- Insertion: O(1)
- Deletion: O(1)
Stack
- Time Complexity:
- Access: O(n)
- Search: O(n)
- Insertion: O(1)
- Deletion: O(1)
Queue
- Time Complexity:
- Access: O(n)
- Search: O(n)
- Insertion: O(1)
- Deletion: O(1)
Hash Table
- Time Complexity:
- Access: O(1)
- Search: O(1)
- Insertion: O(1)
- Deletion: O(1)
About
A comprehensive guide to understanding the time and space complexities of common algorithms and data structures. This repository provides a concise summary of the key concepts in algorithm analysis, presented in an easy-to-read cheat sheet format.
