Time Complexity
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 Rubic'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 |
Complexity Analysis
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. For example, an application that must protect itself from malicious input will avoid naive implementations of quicksort, which has a worst-case time complexity of N2 despite having one of the fastest average-case time complexities compared to all other sorts.