Big-O of Arrays and Objects#

Let’s take a look at time complexity of array and object methods in JavaScript.

Time Complexity#

How much CPU work do our data structures need to perform their basic operations? Let’s take a look.

Big O of Object Operations#

Objects are unordered key/value pairs. Nice to use when order is not needed or required. Most operations on objects are fast. They have no concept of beginning, middle or end.

  • Access → O(1) → direct access to each value by key.

  • Insertion → O(1).

  • Deletion → O(1).

  • Search → O(n), linear time.

Same concrete examples:

  • Object.keys: O(n).

  • Object.values: O(n).

  • Object.entries: O(n).

  • obj.hasOwnProperty: O(1).

Big O of Array Operations#

Arrays are like ordered lists. Use them when order is needed. Some operations are fast, some are not so fast.

  • Access → O(1). Direct access to each value by index.

  • Insertion → O(?). It depends.

    • Insert at index 0 is O(n) because it has to change the index of all other elements.

    • Insert or remove at end of array is O(1). No indexes needs to change.

push() is always faster then shift() and unshift() since push() adds to the end, while shift() and unshift() requires changing the indexes of all other elements because they operate on the beginning of the array.

unshift(val) adds val at position 0 and return val. Moves all other index one index to the right.

Removing at index 0 is O(n) because it has to change the index of all elements. Removing last is O(1) because it doesn’t need to change the index of other elements.

Removing at some other position is O(n) (it depends). Removing elements near the end requires less indexes changes; removing more to the beginning requires more indexes changes.

Space Complexity#

We also have to consider space complexity — how much memory our data structures take.

There is something called auxiliary space complexity, which has to do the space an algorithm requires to perform its computation, not including the input. We will not care about input space, but with the space the algorithm itself needs. Unless otherwise noted, when we say “space complexity”, we’ll be referring to the auxiliary space.

Primitive Types#

Most primitive types are constant space:

  • booleans;

  • undefined;

  • null;

  • numbers;

All of the above are O(1) (constant space). It doesn’t matter if you have x = 1 or x = 1e256. The space required does not change (or not in any significant way).

Strings are not constant space, since their space requirement depends on the length. They are O(n), with n being the length of the string. As the length grows, the space complexity grows.

Reference Types#

For both objects and arrays, it is O(n), n being the number of keys in the object or the length for arrays.

Code Examples#

sum() array#

Following the concept of empty sum, a sum of an empty list results in 0 (zero). That is what Haskell sum Prelude function does, for example:

$ stack exec -- ghci
GHCi, version 9.0.2: https://www.haskell.org/ghc/ :? for help
ghci> sum []
0

Read the Empty sum article on Wikipedia.

Unit Tests#

import { assertEquals } from "/deps.ts";
import { sum } from "./sum-v3.ts";

Deno.test("sum()", async (t) => {
  await t.step("should add nothing", () => {
    assertEquals(sum([]), 0);
  });

  await t.step('should sum a few numbers', () => {
    assertEquals(sum([0]), 0);
    assertEquals(sum([1]), 1);
    assertEquals(sum([-1, -5]), -6);
    assertEquals(sum([-1, 1, -2, 2]), 0);
    assertEquals(sum([1, 2, 3, 4, 1e2]), 110)
  });
});

sum(xs) v1#

/**
 * Sum an all the elements in `xs`.
 *
 * This solution uses a very imperative approach with a for loop.
 *
 * **TIME COMPLEXITY**: O(n). The number of times we add is proportional
 * to the length of the input.
 *
 * **SPACE COMPLEXITY**: O(1). `acc` (a number) is simply added to,
 * which does not cause the algorithm to take any further space than the
 * space require to store a number.
 *
 * @param xs The array of numbers to sum.
 * @return The total.
 */
function sum(xs: number[]): number {
  let total = 0;

  for (let i = 0; i < xs.length; ++i)
    total += xs[i];

  return total;
}

export { sum };

sum(xs) v2#

/**
 * Sum an all the elements in `xs`.
 *
 * This solution uses a reducing function, which makes it a bit FP-ish.
 *
 * **TIME COMPLEXITY**: O(n). The number of times we add is proportional
 * to the length of the input.
 *
 * **SPACE COMPLEXITY**: O(1). `acc` (a number) is simply added to,
 * which does not cause the algorithm to take any further space than the
 * space require to store a number.
 *
 * @param xs The array of numbers to sum.
 * @return The total.
 */
function sum(xs: number[]): number {
  return xs.reduce((acc: number, x: number): number => {
    return acc + x;
  }, 0);
}

export { sum };

sum(xs) v3#

import { add } from "/src/lib/index.ts";

/**
 * Sum an all the elements in `xs`.
 *
 * This solution uses a reducing function, which makes it a bit FP-ish.
 * A function `add` is imported from lib instead of creating an `add`
 * callback on the fly.
 *
 * **TIME COMPLEXITY**: O(n). The number of times we add is proportional
 * to the length of the input.
 *
 * **SPACE COMPLEXITY**: O(1). `acc` (a number) is simply added to,
 * which does not cause the algorithm to take any further space than the
 * space require to store a number.
 *
 * @param xs The array of numbers to sum.
 * @return The total.
 */
function sum(xs: number[]): number {
  return xs.reduce(add, 0);
}

export { sum };

calcSubtotals(xs)#

Unit Tests#

import { assertEquals } from '/deps.ts';
import { calcSubtotals } from './calcSubtotals-v1.ts';

Deno.test('calcSubtotals()', async (t) => {
  await t.step('should produce correct subtotals', () => {
    assertEquals(calcSubtotals([0, 1, 2, 3]), [
      0,             // → 0
      0 + 1,         // → 1
      0 + 1 + 2,     // → 3
      0 + 1 + 2 + 3, // → 6
    ]);
    assertEquals(calcSubtotals([10, 20, 30]), [
      10,           // → 10
      10 + 20,      // → 30
      10 + 20 + 30, // → 60
    ]);
    assertEquals(calcSubtotals([-3, -7, -11]), [
      -3,            // → -3
      -3 + -7,       // → -10
      -3 + -7 + -11, // → -21
    ]);
  });
});

calcSubtotals(xs) v1#

/**
 * Returns the subtotals of the sum of the array elements.
 *
 * @param xs The input array of numbers.
 * @return The array of subtotals.
 *
 * **TIME COMPLEXITY**: `O(n²)`. We have to do a loop inside a loop, and
 * the inner loop eventually runs for the entire length of the input
 * array.
 *
 * **SPACE COMPLEXITY**: `O(n)`. The result array increases as the input
 * array gets larger. For every element in `xs`, we create a new element
 * in the resulting array.
 *
 * A subtotal is the sum of the first element of the array up to each
 * next element in turn. For example, the array `[1, 2, 3, 4]` has these
 * subtotals:
 *
 * ```
 *  1 → sum of just the first element.
 *  3 → sum of 1 and 2.
 *  6 → sum of 1, 2 and 3.
 * 10 → sum of 1, 2, 3 and 4.
 * ```
 *
 * So, for example, the sum of `[1, 2, 3]` produces `[1, 3, 6].
 */
function calcSubtotals(xs: number[]): number[] {
  const subtotals = [];

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

    for (let j = 0; j <= i; ++j) {
      subtotal += xs[j];
    }

    subtotals.push(subtotal);
  }

  return subtotals;
}

export { calcSubtotals };