Big O notation is a way to describe the performance of algorithms. It considers how an algorithm grows with respect to its input. Algorithms that grow slowly when their inout gets larger are considered good algorithms. Algorithms that grow quickly when their input gets larger are considered bad algorithms. We can group algorithms that grow at similar mathematical rates into groups as seen below.
Big O Growth Graph
Big O Table
Here is a table of the above graph (with the addition of n^3).
| Big O Notation | Name |
|---|---|
| O(1) | Constant |
| O(log n) | Logarithmic |
| O(n) | Linear |
| O(n log n) | Linearithmic |
| O(n^2) | Quadratic |
| O(n^3) | Cubic |
| O(2^n) | Exponential |
| O(n!) | Factorial |
In the next modules, we will classify each algorithm into its Big O notation. Each algorithm will have a best, average, and worst case Big O.