Decoding Big O Notation - Time and Space Complexities in JavaScript

Essential Performance Complexities Every Programmer Should Know, Plus Interview-Style Quizzes

Photo by Kevin Ku on Unsplash

Inspired by past fears as a junior developer, I have decided to write a post that tackles the intimidating topic of Big O notation. This post breaks the topic down step by step, ensuring your comfort with the concepts. Plus, you’ll find quiz questions to test your understanding. 🎯

Without further ado, let’s get started!

The Big O

Big O, also known as Big O notation, provides a measure of how an algorithm’s performance scales as the input size, typically denoted as n, increases. It represents the worst-case scenario of the algorithm’s runtime or space usage. By simplifying and focusing on the overall efficiency, Big O allows us to grasp an algorithm’s performance without diving into the specifics of individual code lines or calculations.

When developing algorithms and analyzing their efficiency, it’s crucial to understand the concepts of time and space complexity. These concepts help us measure the performance and scalability of our code.

There are six major types of complexities (time and space):

• Constant: O(1)
• Linear time: O(n)
• Linearithmic time: O(n log n)
• Quadratic time: O(n^2)
• Exponential time: O(2^n)
• Factorial time: O(n!)

Graphical representation of big O time complexities from an article by Adrian Mejia

What is Time Complexity?

Time complexity quantifies the relationship between the running time of an algorithm and the size of the input it operates on, regardless of the kind of machine it runs on. It helps us answer questions like “How does the runtime grow as the input grows?”.
In other words, it is a function of the input size.

Let’s explore some of the most common time complexities, based on their growth rates:

• Constant Time: O(1)— The algorithm takes the same amount of time regardless of the input size. For example, accessing an element in an array by index, or determine the parity of a number.

function isEvenOrOdd(n) {
  return n % 2 ? 'Odd' : 'Even';
}
console.log(isEvenOrOdd(10)); // => Even
console.log(isEvenOrOdd(10001)); // => Odd

• Logarithmic Time: O(log n) — The runtime grows logarithmically (at a decreasing rate) as the input size increases. Common in “divide-and-conquer” algorithms like binary search, which divide your sorted array based on the target value.
  In the example below, the input size reduces by half with every iteration.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // Found the target
    } else if (arr[mid] < target) {
      left = mid + 1; // Target is in the right half
    } else {
      right = mid - 1; // Target is in the left half
    }
  }

  return -1; // Target not found
}

• Linear Time: O(n) — The runtime increases linearly with the input size. For example, iterating through an array.
  By using a single loop, we can say that our function performs O(n) operations, where n represents the length of the input array.

function printAllElements(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}

• Linearithmic Time: O(n log n) — A combination of linear time O(n) and logarithmic time O(log n). The runtime grows in proportion to n multiplied by the logarithm of n. Common in sorting algorithms like merge sort and quicksort.

function quicksort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quicksort(left), pivot, ...quicksort(right)];
}

In the example above, after the recursive calls(O(log n), since the calls are made on smaller sub-arrays), the function combines the sorted left sub-array, the pivot element, and the sorted right sub-array. This concatenation operation takes linear time (O(n)), as it involves copying the elements into a new array. As a result, the time complexity of the quicksort algorithm is considered to be linearithmic (O(n log n)).

• Quadratic Time: O(n^2)— The runtime grows quadratically with the input size. Common in nested loops.

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

• Polynomial Time: O(n^k)(where k is a constant greater than 1, that determines the degree of the polynomial).
  An algorithm with polynomial time complexity typically involves nested loops or iterations, where the number of iterations increases as a power of the input size.
• Exponential Time: O(2^n) — Commonly associated with algorithms that involve recursive branching. The number of recursive calls doubles with each additional element in the input array. As a result, the runtime grows exponentially with the input size, leading to significant performance degradation for larger inputs.

// Example 1 -
// The number of operations doubles with each increase in the input size

const recursiveFibonacci = (n) => {
  if (n < 2) {
    return n;
  }
  return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};

console.log(recursiveFibonacci(6)); // 8

// Example 2 - 
function powerset(n = '') {
  const array = Array.from(n);
  const base = [''];

  const results = array.reduce((previous, element) => {
    const previousPlusElement = previous.map(el => {
      return `${el}${element}`;
    });
    return previous.concat(previousPlusElement);
  }, base);

  return results;
}

In the second example above, the powerset function generates a collection of all the different combinations that can be formed using the elements of the input set.

For each element in the input string, the code doubles the number of subsets generated. This doubling effect is due to the recursive nature of the function. For example, if the input string has one element, the code generates two subsets (an empty set and a set with that element). If the input string has two elements, the code generates four subsets (the previous two subsets plus two more subsets that include the second element).

• Factorial Time: O(n!)— The runtime of an algorithm grows exponentially with the input size. It occurs when an algorithm needs to generate all possible orderings or combinations of elements. It is highly inefficient and becomes quickly impractical even for small input sizes.

function getPermutations(string, prefix = '') {
  if(string.length <= 1) {
    return [prefix + string];
  }

  return Array.from(string).reduce((result, char, index) => {
    const reminder = string.slice(0, index) + string.slice(index+1);
    result = result.concat(getPermutations(reminder, prefix + char));
    return result;
  }, []);
}


getPermutations('ab') // ab, ba...
// n = 2, f(n) = 2;
getPermutations('abc') // abc, acb, bac, bca, cab, cba...
// n = 3, f(n) = 6;
getPermutations('abcd') // abcd, abdc, acbd, acdb, adbc, adcb, bacd...
// n = 4, f(n) = 24;
getPermutations('abcde') // abcde, abced, abdce, abdec, abecd, abedc, acbde...
// n = 5, f(n) = 120;

What is Space Complexity?

Space complexity refers to the amount of memory that an algorithm requires, which is determined by the size of the input. It helps us answer questions like “How much additional memory is needed to run the algorithm?”.

When you create data structures and add more items to your memory, it’s important to consider the space they occupy. Let’s explore some common space complexities, based on their growth rates:

• Constant Space: O(1) — The algorithm uses a fixed amount of memory regardless of the input size. For example, storing a single variable.

function printNumber(n) {
  console.log(n);
}

• Linear Space: O(n)— The memory usage scales linearly with the input size. For example, creating a new array with the same length as the input.

function createArray(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
}

• Quadratic Space: O(n^2)— The memory usage grows quadratically with the input size. Common in algorithms that create a matrix or nested data structures.

function createMatrix(n) {
  const matrix = [];
  for (let i = 0; i < n; i++) {
    const row = [];
    for (let j = 0; j < n; j++) {
      row.push(i + j);
    }
    matrix.push(row);
  }
  return matrix;
}

• Exponential Space: O(2^n) — The memory usage grows exponentially with the input size. Common in algorithms with recursive branching.

function generateSubsets(set) {
  const subsets = [];
  const generate = (currentSet, index) => {
    if (index === set.length) {
      subsets.push(currentSet);
      return;
    }
    generate(currentSet.concat(set[index]), index + 1);
    generate(currentSet, index + 1);
  };
  generate([], 0);
  return subsets;
}

The above function generates all possible subsets of a given set. The number of subsets grows exponentially as the size of the input set increases, resulting in exponential space complexity. Each subset is stored in memory, leading to a rapidly growing space requirement.

Quizzes with Answers

The exercises below will test your ability to analyze scenarios and consider the impact of nested loops, data structures, and algorithms on time and space complexity.

In each question, determine the time and space complexities of the functions involved.

Question 1:

function findSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n) — since the loop iterates through the array once.
Space Complexity: O(1) — since the sum variable is the only additional memory used.

Question 2:

function hasDuplicateValues(arr) {
  const valueSet = new Set();
  for (let i = 0; i < arr.length; i++) {
    if (valueSet.has(arr[i])) {
      return true;
    }
    valueSet.add(arr[i]);
  }
  return false;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n) — as it iterates through the array once, and the Set operations are constant time.
Space Complexity: O(n) — since the Set setValueSet can potentially store all unique values from the array.

Question 3:

function isSorted(arr) {
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      return false;
    }
  }
  return true;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n) — as it iterates through the array once.
Space Complexity: O(1) — as the algorithm only uses memory for a single variable, i.

Question 4:

function findMaxValue(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n) —as it iterates through the array once.

Space Complexity: O(1) — since only one variable (max) is used to track the maximum value.

Question 5:

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n) —as the recursion performs n multiplications, the total number of operations grows linearly with the input size.

Space Complexity: O(n) — The recursive calls create a call stack with space proportional to n.

Question 6:

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(2^n) — Exponential time complexity as the function makes recursive calls for both n — 1 and n — 2.
Space Complexity: O(n) — The call stack grows linearly with the input n.

Question 7:

function mergeArrays(arr1, arr2) {
  return arr1.concat(arr2);
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(m + n) — Linear time complexity as it concatenates two arrays, where m and n are the lengths of the arrays.
Space Complexity: O(m + n) — Linear space complexity as it creates a new array with elements from both input arrays.

Question 8:

function reverseString(str) {
  return str.split('').reverse().join('');
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n) — as it converts the string to an array, reverses the array, and joins it back to a string.
Space Complexity: O(n) —as it creates an array of characters during the splitting operation.

Question 9:

function areAnagrams(str1, str2) {
  const sortedStr1 = str1.split('').sort().join('');
  const sortedStr2 = str2.split('').sort().join('');
  return sortedStr1 === sortedStr2;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n log n) — The sorting operation in the code has a worst-case time complexity of [n log n], where n represents the length of the input strings.

• The split(‘ ’) operation has a time complexity of O(n).
• The time complexity of the sort() method is typically* O(n log n).
• The join(‘ ’) operation has a time complexity of O(n).

* The commonly used sorting algorithms, such as quicksort or mergesort, have an average case time complexity of O(n log n).

Space Complexity: O(n) — as it creates arrays for sorting the strings.

Question 10:

function findIntersection(arr1, arr2) {
  const set1 = new Set(arr1);
  const intersection = [];
  for (let i = 0; i < arr2.length; i++) {
    if (set1.has(arr2[i])) {
      intersection.push(arr2[i]);
    }
  }
  return intersection;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n+m) — Linear time complexity as it constructs a set from arr1 and iterates through arr2.

• The set creation operation has a time complexity of O(n).
• The loop iterates through each element of arr2, resulting in a time complexity of O(m).

Therefore, the overall time complexity is determined by the larger of the two arrays.

Space Complexity: O(m) /O(n)— Linear space complexity as it creates a set with the elements from arr1 and an array to store the intersection.

• The space complexity of creating a Set object from arr1 is O(n), where n is the length of arr1.
• The space complexity of the intersection array is dependent on the number of common elements found between arr1 and arr2. In the worst case, either n or m (length of arr2).
• Other variables used in the code (such as i and the function arguments) have constant space requirements and do not significantly affect the overall space complexity.

Therefore, the overall space complexity of the code is O(n), where n represents the length of the larger array between arr1 and arr2.

Question 11:

function countDistinctElements(arr) {
  const distinctElements = new Set();
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      distinctElements.add(arr[i] + arr[j]);
    }
  }
  return distinctElements.size;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n²) — Quadratic time complexity as there are nested loops iterating over the input array.
Space Complexity: O(n²) — Quadratic space complexity as the distinct combinations of elements are stored in a set.

Question 12:

function findLongestSubstring(str) {
  let maxLength = 0;
  let start = 0;
  const charMap = new Map();
  
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    
    if (charMap.has(char)) {
      start = Math.max(start, charMap.get(char) + 1);
    }
    
    maxLength = Math.max(maxLength, i - start + 1);
    charMap.set(char, i);
  }
  
  return maxLength;
}

🕐

🕓

🕙

Answer:

👀

Time Complexity: O(n) — Linear time complexity as it iterates through the input string once, and the operations inside the loop are constant time.

Space Complexity: O(min(n, m)) — Linear space complexity, where n is the length of the input string and m is the size of the character set. The space used by the charMap will not exceed the size of the character set.

• The space required by the map depends on the number of unique characters in str, which can be at most min(n, m).
• The space complexity includes the variables maxLength, start, and the loop variable i, which require a constant amount of space and do not depend on the input size.

Therefore, considering the space required by charMap and the additional variables, the overall space complexity of the code is O(min(n, m)).

Recap

In this post, we’ve explored the importance of time and space complexity analysis. Time and space complexity analysis is vital for efficient algorithms and optimized code. Big O notation allows us to compare and express these complexities. It helps us make informed decisions for better performance and scalability. We’ve also covered some examples that should give you an idea of how to calculate your running times when developing your projects.

I hope you found this post useful. ✨
Stay tuned for future content! If you’re new here, feel free to explore my other articles, and follow me for updates and more valuable insights.

Resource

By buying me a virtual croissant on Buy Me a Coffee, you can directly support my creative journey. Your contribution helps me continue creating high-quality content. Thank you for your support!