Skip to content

Big O Notation

Or algorithmic worst-case scenarios.

It's inexact by design and explores the "relationship between the size of the problem and the program's running time" (or a schema for dividing problems into different broad classes).

Examples...

  • O(1) - "Big O of one" or "constant time"...the best!
  • O(log n) - Logarithmic...very good!
  • O(n) - Linear...good!
  • O(n^2) - Quadratic time or "Big O of n squared"
  • O(2^n) - "Big O of 2 to the n"...exponential, very bad!
  • O(n!) - "Big O of n factorial"...factorial, extremely bad!

Sorting

Bubble Sort

  • Time: O(n^2)
  • Space: O(1)

Quick Sort

  • Time: avg. O(n log n), worst O(n^2)
  • Space avg. O(log n), worst O(n)

Merge Sort

  • Time: O(n log n)
  • Space: O(n) (worst)

Heap Sort

  • Time: O(n log n)
  • Space: O(1)

Insertion Sort

  • Time: O(n^2)
  • Space: O(1)

Selection Sort

  • Time: O(n^2)
  • Space: O(1)
  • Time: O(n)
  • Space: O(1)

In sorted array or search tree...

  • Time: O(log2 n)
  • Space: O(1)

Depth first search in graph G = (V, E) (worst case)

  • Time: O(|V| + |E|)
  • Space: O(|V|)

Breadth first search (worst case)

  • Time: O(|V| + |E|)
  • Space: O(|V|)

Data Structures

Array

  • Access: O(1)
  • Search: O(n)