JavaScript Algorithms and Data Structures Masterclass

JavaScript Algorithms and Data Structures Masterclass The Missing Computer Science and Coding Interview Bootcamp

Code and Notes from the JavaScript Algorithms and Data Structures Masterclass by Colt Steele

Section 1: Introduction

Curriculum Walkthrough
What order should you watch in?
How I'm running my code

Section 2: Big O Notation

2.1 Intro to Big O

Big O Slides

2.1.1 Objectives

Motivate the need for something like Big O Notation
Describe what Big O Notation is
Simplify Big O Expressions
Define "time complexity" and "space complexity"
Evaluate the time complexity and space complexity of different algorithms using Big O Notation
Describe what a logarithm is

2.1.2 Who Cares?

It's important to have a precise vocabulary to talk about how our code performs.
Useful for discussing trade-offs between different approaches.
When your code slows down or crashes, identifying parts of the code that are inefficient can help us find pain points in our applications.
Less important: it comes up in interviews!

2.2 Timing Our Code

An Example

// add-up-to-slower
function addUpTo(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }

  return total;
}

// Timer
let t1 = performance.now();
addUpTo(1000000000);
var t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`)

// add-up-to-faster
function addUpTo(n) {
  return n * (n + 1) / 2;
}

What does better mean?
- faster?
- less memory-intensive?
- more readable?
The Problem with Time
- Different machines will record different times
- The same machine will record different times!
- For fast algorithms, speed measurements may not be precise enough.

2.3 Counting Operations

rather than counting seconds which are so variable, let's count the number of simple operations the computer has to perform.
depending on what we count, the number of operations can be as low as 2n or as high as 5n + 2
but regardless of the exact number, the number of operations grows roughly proportionally with n
If n doubles, the number of operations will also roughly double.

2.4 Visualizing Time Complexities

Performance Tracker

2.5 Official Intro to Big O

Big O Notation is a way to formalize fuzzy counting. It allows us to talk formally about how the runtime of an algorithm grows as the input grows. We won't care about the details, only the trends.

We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases.

f(n) could be linear (f(n) = n)
f(n) could be quadratic (f(n) = n^2)
f(n) could be constant (f(n) = 1)
f(n) could be something entirely different

2.6 Simplifying Big O Expressions

Constants Don't Matter
- ~~O(2n)~~ => O(n)
- ~~O(500)~~ => O(1)
- ~~O(13n^2)~~ => O(n^2)
Smaller Terms Don't Matter
- O(n + 10) => O(n)
- O(1000n + 50) => O(n)
- O(n^2 + 5n + 8) => O(n^2)
Big O Shorthands
- Arithmetic operations are constant
- Variable assignment is constant
- Accessing elements in an array (by index) or object (by key) is constant
- In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop
A Couple Code Examples

// O(n)
function logAtLeast(n) {
  for (let i = 1; i <= Math.max(5, n); i++) {
    console.log(i)
  }
}

// O(1)
function logAtMost(n) {
  for (let i = 1; i <= Math.min(5, n); i++) {
    console.log(i);
  }
}

O(1) constant time
O(n) linear time
O(n^2) quadratic time