The "O" is for order,as in "Binary search is O(logn);it takes on the order of logn steps to search an array of n items. "
The notation O (f(n)) means that once n gets large ,the running time is proportional to at most f(n), for example , O(n2) or O(nlogn).
| Notation | Name | Example |
|---|---|---|
| O(1) | constant | array index |
| O(logn) | logarithmic | binary search |
| O(n) | linear | string comparison |
| O(nlogn) | nlogn | quick sort |
| O(n2) | quadratic | simple sorting methods |
| O(n3) | cubic | matrix multiplication |
| O(2n) | exponential | set partitioning |
