Big, Bigger, Biggest
The first step to understanding is to become familiar with the different orders of function growth. Let’s consider an example of a classroom with 50 students. The students will give presentations, but the strategy or algorithm of how exactly this is done can vary. We will take this same scenario and discuss a possible algorithm for each classification of function growth. We will see how these different strategies scale as more students are added. We will assume that each presentation takes precisely 60 seconds to complete.
Classification of function growth
Let’s use this example to see different orders of growth. We let n represent the number of students and c and d represent constant values.
Constant
One student is elected to give a single presentation to the rest of the class.
| Function | f(n) = c |
| Presentations | 1 |
| Time | 60 seconds |
| One more student | 0 seconds |
Growth: Doubling the number of students requires no more presentations. No matter how much the number of students increases, there is no effect on the total time this strategy takes. This strategy always takes exactly 60 seconds.
Logarithmic
The class splits into large groups, and each group gives a presentation. The size of the groups grows with the size of the class. There is one group added each time the size of the class doubles. So, for example, with two students there is one group, with four students there are two groups, with 8 students there are three groups, and so on.
| Function | f(n) = c lg(n) |
| Presentations | 5 |
| Time | 5 minutes |
| One more student | 0 seconds |
Growth: Doubling the number of students requires only one more presentation.
Linear
Each student gives a presentation.
| Function | f(n) = c n |
| Presentations | 50 |
| Time | 50 minutes |
| One more student | 60 seconds |
Growth: Doubling the number of students requires twice as many presentations.
Quadratic
Every student picks a single topic. Each student gives a presentation on every topic.
| Function | f(n) = c n^2 |
| Presentations | 2500 |
| Time | 1 day, 17 hours, and 40 minutes |
| One more student | 1 hour and 41 minutes |
Growth: Doubling the number of students requires four times as many presentations.
Cubic
Same as the quadratic strategy, except in addition to students presenting to the entire class, they must also perform each presentation in a one-on-one fashion to each other student.
| Function | f(n) = c n^3 |
| Presentations | 125,000 |
| Time | 86 days, 19 hours, and 20 minutes |
| One more student | 5 days, 7 hours and 31 minutes |
Growth: Doubling the number of students requires eight times as many presentations.
Exponential
Students take turns presenting one at a time. The first student gives two original presentations. Then, for each other student, the student gives a response presentation for each presentation already given before their turn. For example, the first student does two presentations. Then, the second student does a response presentation to the first two presentations. Next, the third student does a response presentation for each of the previous four presentations. Then, the fourth student does eight response presentations, and so on.
| Function | f(n) = c d^n |
| Presentations | 1,125,899,906,842,620 (1.126 quadrillion) |
| Time | approx 35,702,051 years |
| One more student | approx 35,702,051 years |
Growth: Doubling the number of students squares the number of presentations required. Increasing the number of students by just one doubles the number of presentations required.
Factorial
Every student prepares a presentation all on the same topic. The students decide to combine all of their presentations back to back to form one long presentation. However, they want to make sure they get the order perfect, so they practice giving presentations in every possible ordering (permutation).
| Function | f(n) = c n! |
| Presentations | 3.04 x 10^64 (30.4 vigintillion) |
| Time | approx 9.64 x 10^56 or 964 million trillion trillion trillion trillion years |
| One more student | 4.92 x 10^58 years |
Growth: Increasing the number of students by just one more than doubles the required presentations. The rate of growth increases as the size of the class increases.
Tetration
Same as the exponential strategy, except in addition to students presenting to the entire class, they must also perform each presentation in a one-on-one fashion to each other student.
| Function | f(n) = c n^n can also be written as f(n) = n↑↑n (see Knuth’s up arrow notation) |
| Presentations | approx 10^84 |
| Time | approx 10^80 years |
| One more student | approx 10^81 years |
Growth: Increasing the number of students by just one requires many more presentations. The rate of growth increases as the size of the class increases.
Pentation, Hexation, and Beyond
These are functions that contain high order hyperoperations. The growth of these functions is astronomical. It dwarfs exponential, factorial, and even tetration growth and cannot even be easily imagined without a strong mathematical background. These growth rates are almost never used in real-world software engineering, and I only include them here for posterity.
Sub
The prefix “sub” can be applied to any of these classifications to denote a function that grows slower than the classification (i.e., sublinear).
Super
The prefix “super” can be applied to any of these classifications to denote a function that grows faster than the classification (i.e., superquadratic).