Time Complexity Table Cheat Sheet

Strictly Ordered Time Complexity Classes

Efficiency	Notation	Name	Growth Rate Description	Max Input Size (n) for ≈1 Sec
1 (Fastest)	$O(1)$	Constant	Execution time is completely unaffected by input size.	Virtually Infinite
2	$O(\log \log n)$	Double Logarithmic	Grows so slowly that it is practically indistinguishable from constant time.	Virtually Infinite
3	$O(\log n)$	Logarithmic	Highly efficient; the problem space is divided (usually halved) at each step.	Virtually Infinite ($n\approx 10^{300}+$)
4	$O(\sqrt{n})$	Fractional Power / Sublinear	Grows slower than linear, commonly seen in algorithms like search blocks.	$n\approx 10^{16}$
5	$O(n)$	Linear	Scales perfectly 1:1 with the size of the input.	$n\approx 10^8$ (100 million)
6	$O(n{\log }^{\ast }n)$	Iterated Linear	Scaled by the iterated logarithm (which never exceeds 5 for any practical universe-sized input).	$n\approx 10^8$
7	$O(n\log n)$	Linearithmic	Each input element performs a logarithmic operation (the lower bound for comparison sorting).	$n\approx 10^7$ (10 million)
8	$O(n^2)$	Quadratic	Growth scales with the square of the input (standard nested loops).	$n\approx 10^4$ (10,000)
9	$O(n^3)$	Cubic	Growth scales with the cube of the input (triple nested loops).	$n\approx 500$
10	$O(2^n)$	Exponential	The computation time doubles with every single addition to the input size.	$n\approx 25$ to $30$
11	$O(n!)$	Factorial	Grows incredibly fast; scales with all permutations of the input.	$n\approx 11$
12 (Slowest)	$O(n^n)$	Superexponential	The absolute worst scaling; grows faster than factorial.	$n\approx 8$

Common Data Structure Operations

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

Array Sorting Algorithms

Algorithm	Best Time Complexity	Average Time Complexity	Worst Time Complexity	Worst Space Complexity
Quicksort	$\Omega (n\log n)$	$\Theta (n\log n)$	$O(n^2)$	$O(\log n)$
Mergesort	$\Omega (n\log n)$	$\Theta (n\log n)$	$O(n\log n)$	$O(n)$
Timsort	$\Omega (n)$	$\Theta (n\log n)$	$O(n\log n)$	$O(n)$
Heapsort	$\Omega (n\log n)$	$\Theta (n\log n)$	$O(n\log n)$	$O(1)$
Bubble Sort	$\Omega (n)$	$\Theta (n^2)$	$O(n^2)$	$O(1)$
Insertion Sort	$\Omega (n)$	$\Theta (n^2)$	$O(n^2)$	$O(1)$
Selection Sort	$\Omega (n^2)$	$\Theta (n^2)$	$O(n^2)$	$O(1)$
Tree Sort	$\Omega (n\log n)$	$\Theta (n\log n)$	$O(n^2)$	$O(n)$
Shell Sort	$\Omega (n\log n)$	$\Theta (n(\log n{)}^2)$	$O(n(\log n{)}^2)$	$O(1)$
Bucket Sort	$\Omega (n+k)$	$\Theta (n+k)$	$O(n^2)$	$O(n)$
Radix Sort	$\Omega (nk)$	$\Theta (nk)$	$O(nk)$	$O(n+k)$
Counting Sort	$\Omega (n+k)$	$\Theta (n+k)$	$O(n+k)$	$O(k)$
Cubesort	$\Omega (n)$	$\Theta (n\log n)$	$O(n\log n)$	$O(n)$