Big O

Overview

• Runtime Complexity

• Space Complexity

Introduction to Runtime Complexity

Speed

Given numbers in a loop, we want to return those numbers, reversed.

let nums = []
for (let i = 0; i < 10000; i++) {
  nums.push(i)
}
nums = nums.reverse()

let nums = []
for (let i = 0; i < 10000; i++) {
  nums.unshift(i)
}

Right-hand version is hundreds of times slower!

Better solution

Actually, neither of these is the best solution. The fastest solution would be something like this:

let nums = [];
for (let i = 9999; i >= 0; i--) {
  nums.push(i);
}

We Want To Scale

Premature optimization is the root of all evil.

—Donald Knuth

Clear, simpler programs are often better than faster ones

• Please note the “premature:” we don’t want to “micro-optimize”

• But we do care about how they “scale” — that adds up!

Here are times, in nanoseconds, on a fast 2015 Macbook Pro, for pushing versus unshifting n items:

n	push	unshift
10	2	2
100	9	19
1000	73	324
10000	678	21,000
100000	7,810	1,950,000
1000000	84,900	40,323,000,000

Runtime Complexity

What is Runtime Complexity?

How long does it take my program to run
compared to how much workload I have,
where workload is the length of a list.

Why is it Important?

• A mathematical way to talk about algorithm efficiency

• Be aware of the efficiency of your code (and make good choices!)

• Common interview question: “What’s the runtime of this code?”

Example: Sending Data from SLC to NYC

• By sending hard drives on plane

• By sending via cable modem

Can predict times for any # of TB

Notice different “shapes”

• “constant” for plane

• “linear” for modem

Code Example

Say we have this function:

function sumNums(nums) {
  const total = 0;
  for (let num of nums) {
    total += num;
  }
  return total;
}

sumNums([1, 2, 3, 4, 5])

• One operation for initialization of total variable

• One operation for each addition

• Total operations: 1 + (1 × 5)

• = 6 ops

Same Function, Bigger Array

function sumNums(nums) {
  const total = 0;
  for (let num of nums) {
    total += num;
  }
  return total;
}

sumNums([1, 2, 3, ... , 1000000000])

How long will this take?

• One operation for initialization of total variable

• One operation for each addition

• Total operations: 1 + (1 × 1,000,000,000)

• = 1,000,000,001 ops

Graph: A Linear Relationship

• We’re most concerned with large n, since algorithms take less time for small n.

• What we’re interested in is the shape of the graph, or its asymptotic behavior.

Asymptotic Behavior

For any algorithm we drop any factors and constants, and pay attention to the largest growing term. This is how we figure out the asymptotic behavior.

• 1 + (1 × 5)

• 1 + (1 × 1,000,000,000)

• General formula of above: 1 + (1 × n)

• 1 + n

So if your list is n long, it takes n time to do your calculations.

This function is O(n).

For 2n + 3 …

• We can drop the “+ 3” (doesn’t change when we scale)

• We can drop the “2 ×” (we grow in direct proportion to n)

• We’d call {math}`2n + 3` → O(n)

• We can also call it linear time because the graph is a straight line.

What if the constant factor is really big, like 1000n + 1000?

• For n > 1000, it’s still smaller than n²

• Sooner or later, better shapes always win.

Worst Case

function isItemInArray(arr, itemToFind) {
  // Return true if itemToFind is in the array and false otherwise.

  for (let item of arr) {
    if (item === itemToFind) {
      return true;
    }
  }
  return false;
}

• How could we measure the runtime here?

• Do we have to know what is in the array?

We talk pessimistically, only about worst case.

• Not useful to talk about best case:

  • doesn’t happen often (worst case is more likely)

  • most algorithms share best case, e.g. searching best case is always O(1)

• Sometimes we care more about the average case than the worst case, but this is fairly rare.

Common Runtimes

Example

Q: What’s the runtime?

const arr = [5, 48, 88, 24, 14];
console.log(arr[3]);

A: O(1) or constant time

Q: What’s the runtime?

const someObj = {"a": 5, "b": 6, "c": 7}
console.log(someObj.c)

(hint: what if the object had 1,000,000 items in it?)

A: O(1) or constant time

O(1) - Constant Time

• Accessing properties on objects

• Array indexing

O(n) - Linear Time

• A single loop

• Two loops run in succession (2n → O(n))

Multi-Part Algorithms: Addition vs. Multiplication

If arrA and arrB each have n items, what is the runtime of:

for (let a of arrA) {
  console.log(a);
}

for (let b of arrB) {
  console.log(b);
}

A: n + n → 2n → O(n)

Q: What is the runtime of:

for (let a of arrA) {
  for (let b of arrB) {
    console.log(a, b);
  }
}

A: n × n → n² → O(n²)

O(n²) - Quadratic Time

• Two nested for loops

• Bubble sort

• Insertion sort

Logarithmic Runtimes

Guessing Game

I’m thinking of a number between 1 and 100.

Try to guess the number. Every time you guess, I’ll tell you if the guess was too high or too low.

What is the best strategy to guess my number in the fewest guesses?

Here’s the code for the optimal guessing game strategy.

function findNum(maxNum = 100) {
  // Binary search a number between 1 and maxNum.

  // Pick a random target integer between 1 and maxNum.
  const target = Math.ceil(Math.random() * maxNum);
  let min = 1;
  let max = maxNum;
  let guess;

  // while(true) loops forever until we hit a break or return.
  while (true) {
    guess = Math.floor((min + max) / 2); // Math.floor rounds down
    if (guess === target) {
      break;
    } else if (guess > target) {
      max = guess - 1;
    } else {
      min = guess + 1;
    }
  }
  return guess;
}

findNum();

What do you think the runtime is?

Let’s say the target number is 7.

guess	min	max	# possible nums
50	1	49	49
25	1	24	24
12	1	11	11
6	7	11	5
9	7	8	2
7			1

The number of possible numbers gets (approximately) cut in half every time.

• How many times do you have to cut 100 in half before you get 1 (or less)?

• That is the same as the max number of guesses you will need.

• It’s also the same as: How many times do you have to double 1 before you get 100 (or more)?

  • 2^x = 100

• This number x is called the log (base 2) of 100, or log₂ 100.

• So the runtime of the algorithm is O(log n).

Logarithms are assumed to be in base 2

In computer science, we work with binary so much that logarithms are generally assumed to be in base 2. So the 2 is usually not written. But for clarity’s sake, the runtime would be O(log₂ n).

O(log n) - Logarithmic Time

• “Divide and conquer”

• Binary Tree Search

O(n log n) - Linearithmic Time

• More complex “Divide and conquer”

• Efficient sorting algorithms (e.g. merge sort, quick sort)

What’s the Difference?

log n < n < n log n < n²

For n = 1000:

log n	n	n log n	n2
9.97	1000	9970	1,000,000

Less Common (and Slow) Runtimes

O(2ⁿ) - Exponential Time

A common example is Password cracking

• Say there are 72 valid chars for a password

• If password is 1 char there are 72 possibilities

• For 4 chars that’s 72 × 72 × 72 × 72 (or 72⁴) possibilities (26,873,856)

• For 10 chars that’s 72¹⁰ or 3,743,906,242,624,487,424

• For 20: 72²⁰ => 14,016,833,953,562,607,293,918,185,758,734,155,776

O(n!) - Factorial Time

• Graph traversal

• Traveling Salesman problem

Find a path that hits each node once and only once:

• Four choices. Start with one node, say A. [A, …]

• Now there are 3 left, choose 1. [A, C, …]

• Now there are 2 left, choose 1. [A, C, D, …]

• Now there’s only one left. [A, C, D, B]

4 × 3 × 2 × 1 = 4! = 24

There are 24 possible routes to hit every node once.

Space Complexity

What is Space Complexity?

Space complexity is the total space an algorithm will require, based on its input size. Additionally, Space complexity measures how much additional space your algorithm is going to take, based on its actions.

What specifically are we measuring?

Each variable and piece of data takes up space in our RAM. When our function, for example, takes an array and duplicates it, we just took double the RAM. This is Space complexity.

Constant Space

function sum(a, b) {
  let total = a + b;
  return total;
}

In this example, we have a fixed amount of data, making this algorithm an O(1) space complexity. Could it be optimized a little further? Yes, but it is still O(1).

Linear Space

function sum(arr){
  let doubleNums = []
  for(let i = 0; i < arr.length; i++){
    doubleNums.push(arr[i] * 2);
  }
}

In this example, the amount of space taken in RAM is going to be primarily determined by the input size of the array, giving it a Space Complexity of O(n).

Note that array parameters do not take up additional space, as they are simply a reference to an existing array.

Quadratic Space

Imagine a function which takes in a list of N users on a social network, then returns an object describing all the friends within that group.

Input: A list of users

['Jean', 'Cosette', 'Eponine', 'Marius', 'Javert']

Output: A dictionary describing which of the users in the input list are friends with each other

{
  'Marius': ['Eponine', 'Cosette'],
  'Cosette': ['Marius', 'Jean'],
  'Javert': [],
  ...
}

Space Complexity: O(N²) — in the worst case, everybody is friends with everybody else, and each of the N entries in the object is a list of N people.

One More Note On Complexity

Often times we cannot optimize both space and time complexity. It is often a choice, one or the other.

In today’s world, it is more likely that you will want to optimize time complexity over space complexity.

Summary

What is Big O?

Big O notation is a way for us to measure the space and time complexity of our code.