Performance

Mix.install([
  {:kino, github: "livebook-dev/kino", override: true},
  {:kino_lab, "~> 0.1.0-dev", github: "jonatanklosko/kino_lab"},
  {:vega_lite, "~> 0.1.4"},
  {:kino_vega_lite, "~> 0.1.1"},
  {:benchee, "~> 0.1"},
  {:ecto, "~> 3.7"},
  {:math, "~> 0.7.0"},
  {:faker, "~> 0.17.0"},
  {:utils, path: "#{__DIR__}/../utils"}
])

Navigation

Return Home Report An Issue

Setup

Ensure you type the ea keyboard shortcut to evaluate all Elixir cells before starting. Alternatively you can evaluate the Elixir cells as you read.

Big O Notation

As programmers, we are generally more concerned with how performance grows in our program as data becomes larger.

We use Big $$O$$ Notation to communicate about how performance changes based on the size of the data.

• $$O(1)$$: Constant Time
• $$O(log (n))$$: Logarithmic Time
• $$O(n)$$: Linear Time
• $$O(n^2)$$: Quadratic Time (Polynomial Time)
• $$O(2^n)$$: Exponential Time
• $$O(n!)$$: Factorial Time

Here’s a video by Tom Scott for an introductory overview.

Kino.YouTube.new("https://www.youtube.com/watch?v=RGuJga2Gl_k")

As you work with larger amounts of data, different big $O$ complexities grow faster than others. See the graph below for a general ranking.

We should try to be aware of the performance costs and memory costs of both the code that your write, and the built-in functionality you use, especially when working with large amounts of data.

This will inspire both how you write code, and which data structures you choose for particular situations.

Constant Complexity

Did you know that a carrier pigeon can be faster than the internet? It’s true, and it’s related to the nature of constant growth.

Some operations take the same amount of time to execute no matter how much data is involved. For example, a pigeon will travel some distance of kilometers in approximately the same time every attempt. If you strap a USB stick to the pigeon, it can carry (within reason) any amount of data to it’s destination in a constant amount of time.

So a while it makes a great headline about slow internet speed, it’s actually a mathematical guarantee that for some size of data, a pigeon will be faster than the internet.

We can see the nature of how a constant travel time for some amount of data always intersects with the expected internet speed in the graph below.

Utils.graph(:pigeon_beats_internet)

Linear Complexity

Linear growth adds the same number of calculations for each element in the collection. For example, reading a book would (assuming a consistent reading speed) be linear complexity. If you take two minutes to read every page, you add an additional two minute for every page.

• With 1 page it takes 2 minute
• With 2 pages it takes 4 minutes
• With 3 pages it takes 6 minutes
• With 4 pages it takes 8 minutes

In programming terms, for each additional item added to the collection, the computer needs to perform approximately the same number of additional calculations.

Plotted onto a graph you would expect that as we increase the number of elements, time grows in a constant line upward.

Utils.graph(:linear_complexity)

Polynomial Complexity

Rather than grow linearly, polynomial complexity grows to some power. For example, nested loops typically result in polynomial complexity.

That’s because for every element in the first enumerable, we enumerate through every element in the second enumerable.

flowchart
A[1] --> B[1]
A[1] --> C[2]
A[1] --> D[3]

A1[2] --> B1[1]
A1[2] --> C1[2]
A1[2] --> D1[3]

A2[3] --> B2[1]
A2[3] --> C2[2]
A2[3] --> D2[3]

Your Turn

Try changing number to 2, 3, and 4. Notice how it creates more lists, with more elements for each increase in number.

number = 1

Enum.map(1..number, fn _ ->
  Enum.to_list(1..number)
end)

• With 1 element it creates 1 element
• With 2 elements it creates 4 elements
• With 3 elements it creates 9 elements
• With 4 elements it creates 12 elements

In other words, it creates $n^2$ elements. We can see how this grows in the following table.

Utils.table(:n2)

If you nest a third enumeration it becomes $n^3$.

flowchart
A1[1]

A11[1]
A12[2]
A13[3]

A1 --> A11
A1 --> A12
A1 --> A13

A111[1]
A112[2]
A113[3]

A11 --> A111
A11 --> A112
A11 --> A113

A121[1]
A122[2]
A123[3]

A12 --> A121
A12 --> A122
A12 --> A123

A131[1]
A132[2]
A133[3]

A13 --> A131
A13 --> A132
A13 --> A133

B1[1]

B11[1]
B12[2]
B13[3]

B1 --> B11
B1 --> B12
B1 --> B13

B111[1]
B112[2]
B113[3]

B11 --> B111
B11 --> B112
B11 --> B113

B121[1]
B122[2]
B123[3]

B12 --> B121
B12 --> B122
B12 --> B123

B131[1]
B132[2]
B133[3]

B13 --> B131
B13 --> B132
B13 --> B133

C1[1]

C11[1]
C12[2]
C13[3]

C1 --> C11
C1 --> C12
C1 --> C13

C111[1]
C112[2]
C113[3]

C11 --> C111
C11 --> C112
C11 --> C113

C121[1]
C122[2]
C123[3]

C12 --> C121
C12 --> C122
C12 --> C123

C131[1]
C132[2]
C133[3]

C13 --> C131
C13 --> C132
C13 --> C133

Your Turn

Try changing number to 2, 3, and 4. Notice how it creates $n^3$ elements.

number = 3

Enum.map(1..number, fn _ ->
  Enum.map(1..number, fn _ ->
    Enum.to_list(1..number)
  end)
end)

We can see how $n^3$ grows in the following table.

Utils.table(:n3)

Plotted onto a graph, we can see that polynomial complexity results in an upward curve, and the size of the power significantly increases the growth.

Utils.graph(:polynomial_complexity)

Exponential Complexity

In exponential growth, some constant grows by an additional power for each element added to the collection.

Let’s take cracking a password as an example. We can assume a password can only be made from integers 0 to 9.

flowchart LR
0---1---2---3---4---5---6---7---8---9

As the number of digits in the password increases, the number of combinations grows by a power of 2.

• With 1 digit it makes 10 attempts
• With 2 digits it makes 100 attempts
• With 3 digits it makes 1000 attempts
• With 4 digits it makes 10000 attempts

In other words, it executes $$10^n$$ attempts. Now often you’ll see exponential complexity represented as $2^n$ or $C^n$ where 2 or C represents some constant value. In the case of a password cracker, it would be 10.

Utils.table(:exponential_growth)

Utils.graph(:exponential_complexity)

Factorial Complexity

Certain functions enumerate through every possible permutation of the input. As you can imagine this is computationally expensive. For each element, the function needs to enumerate through every remaining element.

For example, if you needed to calculate every permutation of a number, that would require a factorial function.

flowchart
  a[123]
  a --> b[1]
  a --> c[2]
  a --> d[3]
  b --> b1[2] --> 123
  b --> b2[3] --> 132
  c --> c1[1] --> 213
  c --> c2[3] --> 231
  d --> d1[1] --> 312
  d --> d2[2] --> 321

Your Turn

Try adding elements to the list and notice how it creates $n!$ permutations of the list.

defmodule Permutations do
  def of([]) do
    [[]]
  end

  def of(list) do
    for h <- list, t <- of(list -- [h]), do: [h | t]
  end
end

list = [1, 2, 3]
Permutations.of(list)

• With 1 element it creates 1 permutation
• With 2 elements it creates 2 permutations
• With 3 elements it creates 6 permutations
• With 4 elements it creates 24 permutations
• With 5 elements it creates 120 permutations

In other words, it creates $$n!$$ permutations. where $n!$ is a shorthand for

$n! = n (n-1) (n-2) … 1$

For example $5!$ is $5 4 3 2 1$.

Factorial complexity grows incredibly fast, as you can see according to this graph and corresponding data table.

Utils.graph(:factorial_complexity)

Utils.table(:factorial_complexity)

Commit Your Progress

Run the following in your command line from the project folder to track and save your progress in a Git commit.

$ git add .
$ git commit -m "finish big o notation section"