# Analyzing Algorithms 2/6: Function Growth

### 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.

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).