Analyzing Algorithms 2/6: Function Growth

Analyzing Algorithms 2/6: Function Growth

 · 7 min read

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.

Functionf(n) = c
Presentations1
Time60 seconds
One more student0 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.

Functionf(n) = c lg(n)
Presentations5
Time5 minutes
One more student0 seconds

Growth: Doubling the number of students requires only one more presentation.

Linear

Each student gives a presentation.

Functionf(n) = c n
Presentations50
Time50 minutes
One more student60 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.

Functionf(n) = c n^2
Presentations2500
Time1 day, 17 hours, and 40 minutes
One more student1 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.

Functionf(n) = c n^3
Presentations125,000
Time86 days, 19 hours, and 20 minutes
One more student5 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.

Functionf(n) = c d^n
Presentations1,125,899,906,842,620 (1.126 quadrillion)
Timeapprox 35,702,051 years
One more studentapprox 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).

Functionf(n) = c n!
Presentations3.04 x 10^64 (30.4 vigintillion)
Timeapprox 9.64 x 10^56 or 964 million trillion trillion trillion trillion years
One more student4.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.

Functionf(n) = c n^n can also be written as f(n) = n↑↑n (see Knuth’s up arrow notation)
Presentationsapprox 10^84
Timeapprox 10^80 years
One more studentapprox 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).