Big_O_Notation
Big O notation
Intro
Small Big O notation chart Source
Orders of common functions
O(1) constant
Finding the median value for a sorted array of numbers; Calculating ( − 1 ) n
Using a constant-size lookup tableUsing a constant-size lookup table
O(log n) logarithmic
Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a binomial heap
O(n) linear
Finding an item in an unsorted list or in an unsorted array; adding two n-bit integers by ripple carry
O(n^2) quadratic
Multiplying two n-digit numbers by schoolbook multiplication; simple sorting algorithms, such as bubble sort, selection sort and insertion sort; (worst-case) bound on some usually faster sorting algorithms such as quicksort, Shellsort, and tree sort
O(c^n) exponential
Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
O(n!) factorial
Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with Laplace expansion; enumerating all partitions of a set