The Big-O

big-o complexities

Excellent
Good
Fair
Bad
Horrible
N/A

Common data structure operations

Time complexity
Space complexity
Average performance
Worst performance
Worst performance
Data structure
Access
Search
Insertion
Deletion
Access
Search
Insertion
Deletion
Array
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Singly Linked List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Doubly Linked List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(n)
Skip List
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
O(n)
O(n)
O(n)
O(n log(n))
Hash Table
N/A
O(1)
O(1)
O(1)
N/A
O(n)
O(n)
O(n)
O(n)
Binary Search Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
O(n)
O(n)
O(n)
O(n)
Cartesian Tree
N/A
O(log(n))
O(log(n))
O(log(n))
N/A
O(n)
O(n)
O(n)
O(n)
B-Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Red Black Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
Splay Tree
N/A
O(log(n))
O(log(n))
O(log(n))
N/A
O(log(n))
O(log(n))
O(log(n))
O(n)
AVL Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
KD Tree
O(log(n))
O(log(n))
O(log(n))
O(log(n))
O(n)
O(n)
O(n)
O(n)
O(n)

Array sorting algorighms

Time complexity
Space complexity
Array algorithms
Best performance
Average performance
Worst performance
Worst performance
Quicksort
Ω(n log(n))
Θ(n log(n))
O(n^2)
O(log(n))
Mergesort
Ω(n log(n))
Θ(n log(n))
O(n log(n))
O(n)
Timsort
Ω(n)
Θ(n log(n))
O(n log(n))
O(1)
Heapsort
Ω(n log(n))
Θ(n log(n))
O(n log(n))
O(1)
Bubble Sort
Ω(n)
Θ(n^2)
O(n^2)
O(1)
Insertion Sort
Ω(n)
Θ(n^2)
O(n^2)
O(1)
Selection Sort
Ω(n^2)
Θ(n^2)
O(n^2)
O(1)
Tree Sort
Ω(n log(n))
Θ(n log(n))
O(n^2)
O(n)
Shell Sort
Ω(n log(n))
Θ(n log(n)^2)
O(n log(n)^2)
O(1)
Bucket Sort
Ω(n+k)
Θ(n+k)
O(n^2)
O(n)
Radix Sort
Ω(nk)
Θ(nk)
O(nk)
O(n+k)
Counting Sort
Ω(n+k)
Θ(n+k)
O(n+k)
O(k)
Cubesort
Ω(n)
Θ(n log(n))
O(n log(n))
O(n)

About Big O

In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

Big O Notation is a relative representation of an algorithm's complexity. It describes how an algorithm performs and scales by denoting an upper bound of its growth rate.

Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.

Big O complexity chart

Nutshell

  1. Big O is the relative representation of the complexity of an algorithm
  2. It describes how an algorithm performs and scales
  3. It describes the upper bound of the growth rate of a function and could be thought of the worst case scenario