If you can’t explain something in simple terms, you don’t understand it.
- Einstein

Open AI recently released GPT-3 for natural language processing. One of the cool features is the ability to summarize complex passages for a second-grader.

My time in college was spent translating complex Computer Science topics to simple analogies. So I thought I'd share my translation on the holy grail of complex CS topics: time complexity and Big O notation.

This post covers constant, linear, and quadratic time complexities in detail. If you don't know what those mean, read on. If you do and you're looking for logarithms, you'll have to wait on a future post - sorry!

Big O notation is a way to describe how quickly a function grows.
- GPT-3

Let's break down the function first

Say we go through a drive-thru. We drive-in. We order. We pay. We receive our food. We drive out.

The drive-thru is the function. The car is the parameter passed into the function. Order, pay, and food are all steps that occur in the function. And after we complete the steps in the function, we return the car. I'll be using this drive-thru analogy throughout the rest of this post.

function DriveThru(car) {
  order;
  pay;
  food;
  return car;
}

If a drive-thru serves 1,000 cars in a day, it returns 1,000 cars. Every car goes through the same three steps: order, pay, and food.

Why do some cars get through the drive-thru faster than others?

A car can hold N amount of people. For example, a sedan holds five people and a van holds ten people. The drive-thru has no idea how many people are in a car when the car enters. Let's say we have a truck with one person and a van with ten people. And our drive-thru has a strict limit of one payment per vehicle.

The truck quickly proceeds through every step. The van takes a long time on the order and food steps. However, the pay step for both the truck and van takes an equal amount of time.

The time it takes a car to get through the drive-thru is dependant on how many people are in the car. Think of the car as an array of objects. Each object is a person with an order.

car = [
  {
    "name": "Monique",
    "order": "Salad"
  },
  {
    "name": "Joel",
    "order": "Burger"
  }
];

So when we pass the car into the function, the function has to look at each object in every step.

function DriveThru(car) {
  // Order step
  const orders = [];
  for (let i = 0; i < car.length; i++) {
    orders.push(car[i].order);
  }
  sendOrdersToKitchen(orders);

  // Pay step
  sendPaymentToBank(car.creditCard);

  // Food step
  for (let i = 0; i < orders.length; i++) {
    handOrderToCar(orders[i]);
  }

  return car;
}

The payment step is the easiest and fastest step. Because no matter how many people are in the car, there will always be one payment. The order and food steps are dependant on the number of people in the car. If there are five people in one car, the order and food steps run five times before the car can leave.

Let's dig into Big O notation's syntax

Big O follows the following simplified syntax:

O(number of times a step repeats itself in a function)

In CS, "N" or sometimes "K" is used to describe a number of something constant.

For example, let's say N is equal to 5. We have "N cows in a field" which means we have 5 cows in a field. Let's say for every cow, there are twice as many chickens. So we have 5 cows and 10 chickens when N is 5.

To simplify this, we could say we have N cows and N*2 chickens.

Maybe we have cows squared chickens. So we could say we have N cows and N^2 chickens. When N is 5, that would be 5 cows and 25 chickens.

Big O notation uses N to describe the number of steps because we never know how many steps something might take. In our drive-thru, a car might have 1 person or 10 people. We don't know. So we describe them in terms of N because we're worried about measuring the efficiency of the drive-thru not how many people it can handle.

For example, maybe only 5 cars go through Wendys a day, and each car has 1 person. While McDonald's has 1 million busloads go through each day. It would be pointless to compare the efficiency of the drive-thru based on how many people are served. That's why we use N to in Big O notation.

But what about timing the drive-thrus? We could see how long in terms of the time it takes Wendy's and McDonald's to handle 1,000 cars to estimate the efficiency, right?

Yes. Timing is another method of measuring functions. If Wendy's has a poorly run drive-thru, it will take them more time to serve 1,000 cars. However, it would take a lot of experimentation to build an efficient drive-thru based on timing every step.

Big O measures how many steps repeat themselves as the parameter grows. So we can build a drive-thru that limits the amount of repeating steps, without the expensive experimentation.

Let's say McDonald's doesn't enforce one payment per car while Wendy's does. McDonald's now has three steps (order, pay, food) that repeat once for every person in every car. While Wendy's only has two steps (order, food) that repeat once for every person in a car. We can say that Wendy's will be more efficient because they have less repeating steps, without ever timing it in the real world.

Measuring a function with Big O

Big O is a way to measure the efficiency of functions for the best, average, and worst cases. I use to work at McDonald's. The worst-case was a busload of people coming through. The best-case was a car ordering a Sprite. I was always worried about the worst-case, even though it didn't happen very often.

Computer Scientists are always worried about the worst-case too. So let's analyze our drive-thru function for the worst-case scenario and put it into Big O notation.

We have a busload of 30 people come through. The order step repeats 30 times. The payment step repeats once. The food step repeats 30 times.

Or in terms of Big O, the order step runs once for every person. The payment step runs once per car. The food step runs once per person. In Big O notation, N would represent the number of people in each car. So we would have the following:

order: O(n)
pay: O(1)
food: O(n)

When we add up those three steps, we get 1 + n + n which is 1 + 2n. We're worried about the worst-case, so we can ignore the 1 because if we add more people the payment steps always stay the same. We can also write 2n as n because if we add more people there will always be two steps of n.

Our drive-thru function in Big O notation is O(n). In mathematical terms, our time complexity is linear.

If we didn't have the order or food steps, our Big O notation would be O(1). It would have a constant time complexity.

Let's say our kitchen messes up orders a lot when they're overloaded. For every order, they make order squared mistakes. So our order step would still be O(n), our pay step would be O(1), but our food step would be O(n^2).

If we have 5 orders, there would be 25 mistakes on the food. Which means the food step would loop 25 times before getting the order correct. When Big O notation is O(n^2), the time complexity is quadratic.

Quadratic time complexity is often done in code with nested for loops. For example:

const numbers = [1, 2, 3];

for (let i = 0; i < numbers.length; i++) {
  for (let x = 0; x < numbers.length; x++) {
    console.log(numbers[x]);
  }
}

// Output: 1, 2, 3, 1, 2, 3, 1, 2, 3

Graphs illustrate the importance of Big O and time complexity well. Let's say our drive-thru has a linear order time, constant payment time, and quadratic food time.

The graph shows where the bottlenecks in our drive-thru exist before ever actually using the drive-thru. Yes, we could run a test and time 1,000 cars and find the same bottlenecks. But in a real-life scenario that would take a lot of time and be expensive. Analyzing algorithms with Big O notation allow us to find bottlenecks and fix them before we implement them in production.

Another important point is to notice that for 1-3 people, the time or step difference isn't really that much. Big O notation is good at describing worst-case scenarios. Maybe, cars in our drive-thru never have more than one order. If that's the case, optimizing the food step might not be worth it. Instead, we could optimize in other areas, such as installing a second drive-thru.

Code Examples

Here are some common examples of O(1), O(n) and O(n^2)

const myArray = ["dog", "cat", "fish"];

// O(1)
// Output: dog
function constant(myArray) {
  console.log(myArray[0]);
}

// O(n)
// Output: dog, cat, fish
function linear(myArray) {
  for (let i = 0; i < myArray.length; i++) {
    console.log(myArray[i]);
  }
}

// O(n^2)
// Output: dog, cat, fish, dog, cat, fish, dog, cat, fish
function quadratic(myArray) {
  for (let i = 0; i < myArray.length; i++) {
    for (let x = 0; x < myArray.length; x++) {
      console.log(myArray[x]);
    }
  }
}

Conclusion

In programming, we strive for O(n) linear time complexity. O(1) constant time complexity isn't really possible except for simple tasks like addition. O(n^2) should always be avoided. Sometimes algorithms (such as binary search) don't fit any of these, and that's where logarithms come in. I'll update this post with the link to the logarithm article when it's finished!

I hope you have a solid understanding of Big O notation and time complexity now. I'm sure my fast-food analogy could be improved, let me know what you think!