Algorithmic Complexity and Big O Notation

Big O Notation §

$O(1)$ - Constant time

$O(log\cdot n)$ - Logarithmic time

$O(n)$ - Linear time

$O(n\cdot log\cdot n)$ - Log linear time

$O(n^2)$ - Quadratic time

$O(n^3)$ - Cubic time

$O(2^n)$ - Exponential time

$O(n!)$ - Factorial time

Time Complexity §

Data Structure	Access	Search	Insertion	Deletion
Array	$O(1)$	$O(n)$	$O(n)$	$O(n)$
Stack	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Queue	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Doubly-Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$
Hash Table	N/A	$O(1)$	Best: $O(1)$ Worst: $O(n)$	Best: $O(1)$ Worst: $O(n)$
Binary Search Tree	Best: $O(log\cdot n)$ Worst: $O(n)$	Best: $O(log\cdot n)$ Worst: $O(n)$	Best: $O(log\cdot n)$ Worst: $O(n)$	Best: $O(log\cdot n)$ Worst: $O(n)$

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