There are different measurements of the speed of any given algorithm. Given an input size of N, they can be described as follows:

Name | Speed | Description | Formula | Example |
---|---|---|---|---|

factorial time | slower | takes an amount of time proportional to N raised to the Nth power | N! | Brute force solution to Traveling Salesman Problem |

exponential time | slow | takes an amount of time proportional to a constant raised to the Nth power | K^{N} | Brute force solution to Rubik's Cube |

polynomial time | fast | takes an amount of time proportional to N raised to some constant power | N^{K} | Comparison sorts (bubble, insertion, selection sort) |

linearithmic time | faster | takes an amount of time between linear and polynomial | N * log(N) | The Linear logarithmic sorts (quicksort, heapsort, mergesort) |

linear time | even faster | takes an amount of time directly proportional to N | K * N | Iterating through an array |

logarithmic time | much faster | takes an amount of time proportional to the logarithm of N | K * log(N) | Binary Search |

constant time | fastest | takes a fixed amount of time, no matter how large the input is | K | Array index lookup |

A given operation can have different time complexities with different orders/sets of input. The different methods of time complexity analysis are as follows:

Name | Description | Example |
---|---|---|

best-case | A case where the operation executes as fast as it possibly can | Bubblesort has a best-case time complexity of N. |

average-case | A case where the operation executes in a time comparable to the majority of possible cases | Quicksort has an average-case time complexity of N * log(N) |

worst-case | A case where the operation executes as slowly as it possibly can | Quicksort has a worst-case time complexity of N^{2} |

amortized worst-case | The average worst-case taken over an infinite number of inputs | vector::push_back() has an amortized worst-case time complexity of K (constant time) |

Choosing the right algorithm depends upon which cases you expect your application to encounter.