Section 8.10 Big-O
As we saw on the last page, the exact way in which we count units of work in an algorithm is not as important as the degree to which the algorithm depends on the size of its input. An algorithm that always involves the same amount of work is more efficient than one where the work grows as a function of the input size (at least once we pass a certain problem size).
We can further divide the algorithms where work grows as a function of input size into categories based on what kind of function determines the growth. This is the idea behind what is known as Big-O classification: assigning algorithms to a class of functions that describe their growth. Some common categories are Constant , Linear, Logarithmic and Quadratic; their relative growths are shown in the figure below.
To write that an algorithm is in a particular class, we say that it is \(O(n)\) or \(O(log(n))\text{.}\) Spoken, we would say something like: “Oh of n” or “Oh of log n”.
- Constant
-
\(O(1)\)Any algorithm that takes a constant amount of work. It could be 4 steps or 100 steps, the important thing is that the amount of work does not depend on the input to the algorithm.Examples:
- DrawSquare of size n.
- Looking at a class roster and deciding if there are any students enrolled - I can say “Yes” or “No” in the same amount of time whether there are 0 names, 3 names or 100 names on the roster.
- Logarithmic
-
\(O(log(n))\)Any algorithm where the relationship between work f(n) and input n is described by a logarithmic function. It could be \(f(n) = log_2(n)\) or \(f(n) = 3 \cdot log_{10}(n)\text{.}\) Note that we don’t care what base the logarithm is.We will see an example of this category soon…
- Linear
-
\(O(n)\)Any algorithm where the relationship between work f(n) and input n is described by a linear function. It could be \(f(n) = \frac{n}{2} - 4\) or \(f(n) = 5n + 100\text{.}\)Examples:
- DrawShape with n sides.
- Looking for the highest score in a stack of tests - if the stack gets twice as big, it will take me twice as long to look through them all.
- Quadratic
-
\(O(n^2)\)Any algorithm where the relationship between work f(n) and input n is given by quadratic function like \(f(n) = 5n^2 + 2\text{.}\)Examples:
- Given a number n, laying out a n by n grid of cones. (If n is 5 there are 25 cones to layout, if n = 10 there are 100 cones to place). In that case n doubled, but the work (number of cones to place) increased by 4x!
- Or sorting a stack of papers alphabetically - if the size of the stack doubles, sorting them is going to take me more than double the time.
If the function that describes the work for an algorithm has multiple terms, we classify it only according to its fastest-growing term. \(f(n) = n^2 + 2n\) would be considered Quadratic because for large values of n the \(n^2\) will dominate. Say n is 100: \(n^2 = 10,000\) and \(2n = 200\)… the extra 200 hardly even matters compared to the 10,000.
You have attempted of activities on this page.
