Big-O Complexity Reference

This cheatsheet provides a quick reference for common Big-O time and space complexities of algorithms and data structures, helping you understand their performance characteristics.

Installation

This is a conceptual reference, not a tool to be installed.

Core Concepts

• Big-O Notation: A mathematical notation used to describe the upper bound of an algorithm’s time or space complexity. It focuses on how the execution time or memory usage grows as the input size increases, ignoring constant factors and lower-order terms.
• Time Complexity: Measures how the execution time of an algorithm scales with the input size.
• Space Complexity: Measures how the memory usage of an algorithm scales with the input size.
• n: Represents the size of the input to the algorithm.

Common Complexities

Here are the most frequently encountered Big-O complexities, ordered from best to worst performance for time complexity:

Constant Time: O(1)

• Description: The execution time does not depend on the input size.
• Examples:
  • Accessing an element in an array by index: array[5]
  • Pushing/popping from a stack (if implemented with an array or linked list): stack.push(item)
  • Inserting/deleting at the beginning/end of a doubly linked list: list.insert_head(item)
  • Basic arithmetic operations: a + b

Logarithmic Time: O(log n)

• Description: The execution time grows logarithmically with the input size. This typically occurs when the problem size is halved in each step.
• Examples:
  • Binary search on a sorted array: binary_search(sorted_array, target_value)
  • Finding an element in a balanced binary search tree: bst.find(key)
  • Heap operations (insert/delete-min) in a binary heap: heap.insert(value)

Linear Time: O(n)

• Description: The execution time grows linearly with the input size.
• Examples:
  • Iterating through all elements of an array or list: for item in list: print(item)
  • Finding the maximum or minimum element in an unsorted array: max(array)
  • Linear search: linear_search(array, target_value)
  • Hash table operations (average case for insertion, deletion, lookup): hash_table.get(key)

Linearithmic Time: O(n log n)

• Description: The execution time grows by a factor of n multiplied by the logarithm of n. Often seen in efficient sorting algorithms.
• Examples:
  • Merge sort: merge_sort(array)
  • Heap sort: heap_sort(array)
  • Quick sort (average case): quick_sort(array)

Quadratic Time: O(n²)

• Description: The execution time grows quadratically with the input size. Typically involves nested loops iterating over the input.
• Examples:
  • Bubble sort: bubble_sort(array)
  • Selection sort: selection_sort(array)
  • Insertion sort (worst case): insertion_sort(array)
  • Finding all pairs of elements in an array: for i in array: for j in array: ...

Cubic Time: O(n³)

• Description: The execution time grows cubically with the input size. Usually involves triple nested loops.
• Examples:
  • Some matrix multiplication algorithms: matrix_multiply(matrix_a, matrix_b)
  • Triple nested loops iterating over the input: for i in data: for j in data: for k in data: ...

Exponential Time: O(2ⁿ)

• Description: The execution time doubles with each addition to the input size. Often associated with brute-force solutions to problems that can be solved more efficiently.
• Examples:
  • Finding all subsets of a set: generate_subsets(set)
  • Recursive Fibonacci calculation (naive): fibonacci(n)
  • Traveling Salesperson Problem (brute-force solution): tsp_brute_force(cities)

Factorial Time: O(n!)

• Description: The execution time grows extremely rapidly, proportional to the factorial of the input size.
• Examples:
  • Permutations of a set: generate_permutations(list)
  • Traveling Salesperson Problem (complete enumeration of all permutations): tsp_permutation(cities)

Space Complexity Examples

Similar to time complexity, space complexity describes how memory usage scales.

O(1) Space

• Description: Constant extra space is used, regardless of input size.
• Examples:
  • In-place sorting algorithms like Heap Sort.
  • Basic arithmetic operations.
  • Iterating through an array without storing intermediate results.

O(n) Space

• Description: Linear extra space is used, proportional to the input size.
• Examples:
  • Storing elements in a new array or list.
  • Recursion depth proportional to n (e.g., naive recursive Fibonacci).
  • Hash tables that store all elements.

O(n²) Space

• Description: Quadratic extra space is used.
• Examples:
  • Storing an n x n matrix.
  • Algorithms that require storing all pairs of elements.

O(log n) Space

• Description: Logarithmic extra space is used.
• Examples:
  • Recursion depth in algorithms like Quick Sort (if not in-place) or Merge Sort.
  • Binary search tree traversal.

Common Data Structure Complexities

Gotchas

• Average vs. Worst Case: Many data structures (like hash tables and quicksort) have excellent average-case performance but degrade significantly in the worst case. Always consider which scenario is more relevant to your application.
• Constant Factors Matter in Practice: Big-O ignores constant factors, but in real-world scenarios, a large constant factor can make an algorithm with a better Big-O complexity perform worse than an algorithm with a worse Big-O but a smaller constant factor for small input sizes.
• Recursion Stack Space: Recursive algorithms can consume significant stack space, contributing to their space complexity, which might not be immediately obvious from the algorithmic logic alone.
• "Big O of n" vs. "Big O of log n": Be precise with your language. "Big O of n" refers to O(n), not O(log n).
• Not All O(n log n) are Equal: While Merge Sort and Heap Sort are both O(n log n), their constant factors and memory usage can differ.
• Amortized Analysis: Some operations, like resizing in dynamic arrays (e.g., Python’s list or C++'s std::vector), have a high cost occasionally but a low average cost over a sequence of operations. This is known as amortized analysis, and operations like list.append() in Python are often described as O(1) amortized.