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 | KN | Brute force solution to Rubik's Cube |
| polynomial time | fast | takes an amount of time proportional to N raised to some constant power | NK | 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 N2 |
| 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.