Notation Name Example
O(1), constant Determining if a number is even or odd; using a constant-size lookup table or hash table
O(log log n), double logarithmic Finding an item using interpolation search in a sorted array of uniformly distributed values.
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^c),;0<c<1 fractional power Searching in a kd-tree
O(n), 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.
O(nlog n)=O(log n!), linearithmic, loglinear, or quasilinear Performing a Fast Fourier transformheapsortquicksort (best and average case), or merge sort
O(n^2), 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
O(n^c),;c>1″ /></td>
<td><a title=polynomial or algebraic Tree-adjoining grammar parsing; maximum matching for bipartite graphs
L_n[alpha,c],;0 < alpha < 1=,
e^{(c+o(1)) (ln n)^alpha (ln ln n)^{1-alpha}}
L-notation or sub-exponential Factoring a number using the quadratic sieve or number field sieve
O(c^n),;c>1″ /></td>
<td><a title=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 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
File:Selection sort animation.gif
  • You pick up smallest first, then 2nd smallest, then 3rd…
  • Average Case: O(n^2)








Bubble Sort

  • Swap pairs until sorted

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.