Algorithms
Notation | Name | Example |
---|---|---|
![]() |
constant | Determining if a number is even or odd; using a constant-size lookup table or hash table |
![]() |
double logarithmic | Finding an item using interpolation search in a sorted array of uniformly distributed values. |
![]() |
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. |
![]() |
fractional power | Searching in a kd-tree |
![]() |
linear | Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers byripple carry. |
![]() |
linearithmic, loglinear, or quasilinear | Performing a Fast Fourier transform; heapsort, quicksort (best and average case), or merge sort |
![]() |
quadratic | Multiplying two n-digit numbers by a simple algorithm; bubble sort (worst case or naive implementation), Shell sort, quicksort (worst case), selection sort or insertion sort |
![]() |
Tree-adjoining grammar parsing; maximum matching for bipartite graphs | |
![]() ![]() |
L-notation or sub-exponential | Factoring a number using the quadratic sieve or number field sieve |
![]() |
Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search | |
![]() |
factorial | Solving the traveling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors. |
Insertion Sort
- You pick up a card, start at the beginning of your hand and find the place to insert the new card, insert it and move all the others up one place.
- Best Case: O(n) on a sorted list because must go through every number to check to see if it is in the right spot
- Worst Case: O(n^2) on a reversed list because must take out first, shift everything over, insert at end, then repeat for all
- Average Case: O(n^2)
Selection Sort

- You pick up smallest first, then 2nd smallest, then 3rd…
- Average Case: O(n^2)
Bubble Sort
- Swap pairs until sorted