# Problem Solving: Order of complexity

< A-level Computing | AQA | Paper 1 | Theory of computation

Jump to navigation
Jump to search

## Order of Complexity[edit]

Notation | Name | Example |
---|---|---|

constant | Determining if a number is even or odd; using a constant-size lookup table | |

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. | |

linear | Finding an item in an unsorted list or a malformed tree (worst case) or in an unsorted array; Adding two n-bit integers by ripple 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
| |

polynomial or algebraic | Tree-adjoining grammar parsing; maximum matching for bipartite graphs | |

exponential | 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 travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with expansion by minors. |