Time Complexity, Space Complexity, and Big O Notation

This is the first post in my series Data Structures & Algorithms using JavaScript. As a boot camp grad, I found that once I started my professional career in software development, there was a gap in my fundamentals knowledge. Although I am not reversing a binary tree day-in-and-day-out, I do think it is important to learn these fundamentals simply because you will be a better developer by knowing they exist. This week I start things off by discussing Time and Space Complexity, and how you can use Big O notation to determine these metrics.

Time Complexity

A measurement of computing time that an algorithm takes to complete

What causes time complexity?

• Operations (+, -, *, /)
• Comparisons (>, <, ==)
• Looping (for, while)
• Outside function calls (function())

Big O Notation

The language and metric we use for talking about how long it takes for an algorithm to run

O(1) Constant Time

Not bound by the size of an input, only one operation is performed

• Direct query of data you are looking for
• No iterating (loops) are involved

If you know the precise location of data you want to pull out of an Object {} or Array [], you can query for that item without having to iterate or perform any additional computation.

Most of the time, if you're using Constant Time, you are in good shape from a performance standpoint.

Let me show you an example in which I perform tasks that evaluate to Constant Time:

const jedi = ['luke', 'anakin', 'obi wan', 'mace windu', 'yoda', 'darth vader'];

function findAJedi(jediList) {
  console.log(jediList[1]) // O(1)
}

findAJedi(jedi) // O(1)

First, I use the const keyword to declare a new variable with the identifier jedi and give this variable a collection of string values

const jedi = ['anakin', 'luke', 'obi wan', 'mace windu', 'yoda', 'darth vader'];

Next, I use the function keyword to create a new function and give it the identifier findAJedi. This function will have a single parameter with an identifier of jediList

function findAJedi(jediList) {

Using bracket notation [] I pull out the entry that is in index position 1

function findAJedi(jediList) {
  console.log(jediList[1]) // O(1)
}

Since we already know where the data we want is, and we do not have to loop to get there, this operation is O(1) or Constant Time

We call the findAJedi function with the variable jediList as the single argument and our findAJedi function prints anakin. He is the chosen one, right?

findAJedi(jedi)
// anakin

O(n) Linear Time

Bound by the input, time increases linearly as input increases

• Involves iteration to find a value
  • for loops
  • while loops

Let me show you an example of an operation that evaluates to O(n) or Linear Time:

const jedi = new Array(5).fill("luke")

function findLuke(jediList) {
  for (let i = 0; i < jediList.length; i++) {
    if (jediList[i] === "luke") {
      console.log("found luke")
    }
  }
}

findLuke(jedi)

First, we use the const keyword to create a new variable with the identifier jedi that is assigned the value of an Array. We use the fill() method to populate this Array with five luke values that are of type string

const jedi = new Array(100).fill("luke")

Next, we use the function keyword to create a new function with an identifier findLuke. This function will have a single parameter with an identifier of jediList

function findLuke(jediList) {

Inside of our findLuke function use the for keyword to create a for loop. We iterate through our jediList and use bracket notation [] to compare each entry to luke, when we find a match we console.log it

for (let i = 0; i < jediList.length; i++) {
  if (jediList[i] === "luke") {
    console.log("found luke")
  }
}

Since we are iterating through the entire Array, our Big O would be O(n). Right now our jediList only has five entries, but what if we had 10,000, or 1,000,000,000? These are good considerations to think about as you write code.

We call our findLuke function that takes a single argument jedi and since all of our entries are luke, we console.log luke five times

findLuke(jedi)
// found luke
// found luke
// found luke
// found luke
// found luke

O(n²) Quadratic Time

Often thought of as "worst case", multiple nested iterations occur

• Involves two nested loops
• Each item in two collections need to be compared to each other

I am sure that you have been here before, I know I sure have. Nesting loops is never a good idea and there is a good reason for that. Speaking in terms of Big O, when you are iterating over a collection, and then iterating again inside of that first iteration that will produce a Big O of O(n^2)

Let me show you an example of a function that produces a Big O of O(n^2):

const jedi = ['mace windu', 'yoda', 'obi wan'];

function logJediDuos(jediList) {
  for (let i = 0; i < jediList.length; i++) {
    for (let j = 0; j < jediList.length; j++) {
      console.log(jediList[i], jediList[j]);
    }
  }
}

logJediDuos(jedi);

First, we use the const keyword to create a new variable with the identifier jedi that is assigned to an Array of three string values

const jedi = ['mace windu', 'yoda', 'obi wan'];

Next, we use the function keyword to create a new function with an identifier of logJediDuos. This function has a single parameter jediList

function logJediDuos(jediList) {

Inside of logJediDuos we use the for keyword to create our first for loop. In our for statement we declare that we want to iterate through the length of jediList until that length is greater than the value of i. We increase the value of i after each iteration

for (let i = 0; i < jediList.length; i++) {

Inside of the previous for loop, we create another for loop. Inside of our for statement we make sure to give our index variable an identifier of j to ensure we do not mutate the state of our i variable.

Using bracket notation [] we use our index variables i and j to console.log each pair inside of our jediList

for (let i = 0; i < jediList.length; i++) {
  for (let j = 0; j < jediList.length; j++) {
    console.log(jediList[i], jediList[j])
  }
}

When we invoke our logJediDuos function we get this result:

logJediDuos(jedi)
// mace windu mace windu
// i = 0, j = 0
// mace windu yoda
// i = 0, j = 1
// mace windu obi wan
// i = 0, j = 2
// yoda mace windu
// i = 1, j = 0
// yoda yoda
// i = 1, j = 1
// yoda obi wan
// i = 1, j = 2
// obi wan mace windu
// i = 2, j = 0
// obi wan yoda
// i = 2, j = 1
// obi wan obi wan
// i = 2, j = 2

I am only covering a handful of common Big O times in this post. If you want to learn more about advanced Big O times you can do so by following the links provided below:

O(n!) Factorial Time

Adds a nested loop for every loop

Read more here

O(log N) Logarithmic

Involves searching algorithms if sorted

Read more here

O(2^N) Exponential

Recursive algorithms that solve a problem of size N

Read more here

Simplifying Big O

• Always assume worst-case scenario
• Remove constants
• Different terms for inputs
• Drop non-dominants

Always assume worst-case scenario

It is a very common practice to iterate through a list of data in your program, and lists can vary greatly in size. When I say to always assume worst-case scenario I mean that in a few different ways.

• If you query for data, assume it is the last item in the list

• Assume the list you're iterating through will get bigger

• Assume some machines will run your algorithm slower than on your machine

Remove constants

When we are determining the Big O of an algorithm it helps to remove repeated measurements (constants). This allows us to get a more clear read on the speed of the algorithm by removing unneeded calculation.

Let me show you an example where we remove constants:

function printJedi(jediList) {
  jediList.forEach((jedi) => {
    console.log(jedi)
  }
  // O(n)

  jediList.forEach((jedi) => {
    console.log(jedi)
  }
  // O(n)
}

printJedi(['anakin', 'obi wan', 'yoda'])

// O(n) + O(n) = O(2n)

First, we create a new function with the identifier printJedi, this function has a single parameter (jediList)

function printJedi(jediList) {

Inside of our printJedi function we call the forEach() method on jediList two separate times

jediList.forEach((jedi) => {
  console.log(jedi)
}
// O(n)

jediList.forEach((jedi) => {
  console.log(jedi)
}
// O(n)

Since we are iterating through the entire jediList array, each operation is O(n). At the end of our function, we add up our Big O (O(n) + O(n)) which results in O(2n). We can simplify this by removing the constants which in this case is 2. After this, we are left with Big O of O(n).

Different terms for inputs

In cases that you iterate through different pieces of data, the Big O calculation will reflect that. Since each collection of data will most likely be different sizes, the consideration of its time complexity comes into play.

Let me show you an example of calculating Big O while using multiple collections of data:

function printJediAndSith(jediList, sithList) {
  jediList.forEach(jedi => console.log(jedi));

  sithList.forEach(sith => console.log(sith));
}


printJediAndSith(['anakin', 'obi wan'], ['vader', 'sidious']);

// O(a + b)

Above, we create a new function with the identifier printJediAndSith, this function has two parameters: jediList and sithList

function printJediAndSith(jediList, sithList) {

Inside of printJediAndSith we call the forEach() method on the jediList array and the sithList array

jediList.forEach(jedi => console.log(jedi));

sithList.forEach(sith => console.log(sith));

Now, what do you think the Big O is of the printJediAndSith function? Since we iterate through a collection of data it should be O(n), right? Not in this case.

Remember, these parameters will likely have different lengths. It is because of this that we determine the Big O of printJediAndSith to be O(a + b).

Drop non-dominants

Inside of functions a lot of different things can happen. This includes the range of time complexity as well. When determining the Big O of an algorithm, for the sake of simplifying, it is common practice to drop non-dominants. In short, this means to remove or drop any smaller time complexity items from your Big O calculation.

Let me show you an example of dropping non-dominants:

function printAndSumJediAttendance(jediList) {
  jediList.forEach(list => console.log(list));

  jediList.forEach(firstList => {
    jediList.forEach(secondList => {
      console.log(firstList + secondList)
    });
  });
}

printAndSumJediAttendance([1983, 66, 1138, 94, 1977])

First, we create a new function with the identifier printAndSumJediAttendance, this function has a single parameter jediList

function printAndSumJediAttendance(jediList) {

Inside of printAndSumJediAttendance we call the forEach() method on the jediList parameter. Because we are iterating through a collection of data this Big O evaluates to O(n).

jediList.forEach(list => console.log(list))

On the next line, we call the forEach() method on our jediList parameter. Inside of this forEach block, we call forEach on jediList again. Because we are iterating through nested loops, our Big O evaluates to O(n^2)

jediList.forEach(firstList => {
  jediList.forEach(secondList => {
    console.log(firstList + secondList)
  });
});

Let me break this Big O calculation down a bit:

function printAndSumJediAttendance(jediList) {
  // O(n)
  jediList.forEach(list => console.log(list));

  // O(n^2)
  jediList.forEach(firstList => {
    jediList.forEach(secondList => {
      console.log(firstList + secondList)
    });
  });
}
// O(n + n^2) -> simplified -> O(n^2)

As you can see, if we add up the Big O calculations from this function, we are left with a result of O(n + n^2).

If we analyze this, we see that the part of our calculation with the largest Big O is n^2 - because of this, we drop the n. We do this because n^2 is more dominant than n. Once we have refactored our calculation, we are left with this result: O(n^2).

Space Complexity

parallel to time complexity, space complexity is the measurement of memory (space) that an algorithm needs

What causes Space Complexity?

• Variables
• Data structures
• Function calls
• Allocations

Let me show you an example of how we would calculate the space complexity:

function buildALightsaber(pieces) {
  let totalPieces = 0; // O(1)
  totalPieces = 4; // O(1)

  for (let i = 0; i < pieces.length; i++) { // O(n)
    addCrystals(); // O(n)
    const hasTheForce = true; // O(n)
    totalPieces++; // O(n)
  }
  return totalPieces; // O(1)
}

// O(3 + 4n) -> simplified -> O(n)

First, we create a new function with the identifier buildALightsaber that has a single parameter pieces

function buildALightsaber(pieces) {

Inside of buildALightsaber, we use the let keyword to create a new variable with the identifier totalPieces that is assigned to the value 0. On the following line, we reassign the variable totalPieces to the value of 4

Creating and assigning values to variables is O(n) (constant time); therefore, these two steps are both O(1)

let totalPieces = 0; <-- // O(1)
totalPieces = 4; <-- // O(1)

Next, we create a for loop and iterate through pieces

Since we are going to be iterating through a collection of data, the Big O of this operation will evaluate to O(n)

for (let i = 0; i < pieces.length; i++) { <-- // O(n)

Inside of our for loop, we call a function with an identifier addCrystals(). Next, we use the const keyword to create a variable with the identifier hasTheForce and assign it the value true. Last, we increment our totalPieces by one.

In terms of evaluating space complexity while calling functions, creating variables, and updating the values of variables inside of an iteration (for or while loops), you have to be mindful of the fact that these actions will occur for each iteration. It is because of this that all actions mentioned will be O(n)

addCrystals(); <-- // O(n)
const hasTheForce = true; <-- // O(n)
totalPieces++; <-- // O(n)

After we finish iterating through pieces we return the value of totalPieces

Since this is a single action, the Big O is evaluated to O(1) or constant time

return totalPieces; <-- // O(1)

If we calculate the Big O of this function we originally get (3 + 4n). After we apply our principles of simplifying Big O, we know that we can remove constants which will make our final result O(n)

In Summary

I hope after reading this you have a solidified idea of how time and space complexity work, what their importance is in the functions/algorithms we write, and how we can calculate these complexities using Big O notation.

Next week I will begin to take a deep dive into arguably the most popular data structure JavaScript developers use, the Array. See you then!