In Chapter 13, Sorting and Searching Algorithms, we introduced the concept of big O notation. What does it mean, exactly? It is used to describe the performance or complexity of an algorithm. Big O notation is used to classify algorithms according to how much time it will take for the algorithm to run, depending on space/memory requirements as the input size grows.
When analyzing algorithms, the following classes of function are most commonly encountered:
| Notation | Name |
| O(1) | Constant |
| O(log(n)) | Logarithmic |
| O((log(n))c) | Poly-logarithmic |
| O(n) | Linear |
| O(n2) | Quadratic |
| O(nc) | Polynomial |
| O(cn) | Exponential |
