Time complexity
table of common time complexities
| Name | Running time T(n) | Example Algorithms |
|---|---|---|
| constant time | O(1) | determining if an integer is even or odd |
| logarithmic time | O(log(n)) | Binary Search |
| linear time | O(n) | Finding the smallest item in an unsorted array |
| quasilinear time | O(nlog(n)) | fastest comparison sort |
| quadratic time | O(n^2) | Insertion sort |
| cubic time | O(n^3) | naive multiplication of two nxn matrics. |
| polynomial time | 2^O(log(n)) = ploy(n) | |
| exponential time(with linear exponent) | O(2^n), O(C^n) | solving the traveling salesman problem using dynamic programming |
| factorial time | O(n!) | solving the traveling salesman problem via brute-force search |