A Programmer’s Guide to Types and Data Structures in JavaScript


Data structures are fundamental tools in programming, enabling us to efficiently store, manipulate, and access data. In JavaScript, a language known for its flexibility, mastering these structures can significantly enhance your ability to solve problems and write optimal code.

In this blog post, we’ll explore commonly used data structures in JavaScript. By understanding both the “how” and the “why” of these data structures, you’ll be better equipped to tackle complex problems. As always, we start simple.


Primitive Types

JavaScript’s primitive types form the foundation of all data manipulation. We can consider that there are 3 main primitive data types: strings, numbers and booleans.

Strings

In JavaScript, strings are a fundamental data type used to represent textual data. A string is essentially a sequence of characters, numbered from 0, for the first character, enclosed within single quotes (’ ’), double quotes (” “), or backticks ( ). Strings are immutable, meaning once created, their content cannot be altered—any modification results in the creation of a new string.

You can create strings in several ways:

  • Using Single or Double Quotes
let singleQuoteString = 'Hello, World!';
let doubleQuoteString = "JavaScript is fun!";

Both are functionally identical. The choice is often based on stylistic preference or the need to include quotation marks within the string.

  • Using Backticks (Template Literals)

Backticks allow for multiline strings :

let multiline = `This is
a multiline
string.`;
console.log(multiline);

JavaScript uses something called escape sequences to include special characters within strings.

Escape SequenceDescription
\’Single quote
\”Double quote
\\Backslash
\nNewline
\tTab
\bBackspace
\rCarriage return
let quote = "She said, \"JavaScript is awesome!\"";
console.log(quote); // She said, "JavaScript is awesome!"

let multiline = "Line1\nLine2\nLine3";
console.log(multiline);
// Output:
// Line1
// Line2
// Line3

JavaScript uses UTF-16 encoding, allowing the use of Unicode characters.

let smiley = "\u263A";
console.log(smiley); // ☺

String manipulation will be addressed in a dedicated blog post.

Numbers

In JavaScript, numbers are a fundamental data type used to represent both integers and floating-point values. JavaScript has two primary numeric types:

  • Number (the default type for all numeric values)
  • BigInt (for very large integers beyond the safe range of Number)
let integer = 42;        // Integer
let float = 3.14; // Floating-point number
let negative = -100; // Negative number
let scientific = 1e6; // Scientific notation (1 * 10^6 = 1000000)
let bigNumber = 1234567890123456789012345678901234567890n;
console.log(bigNumber); // BigInt representation with 'n' at the end

You can represent numbers in different formats:

  • Decimal (Base 10):
let decimal = 255;
  • Binary (Base 2): Prefixed with 0b
let binary = 0b11111111; // 255 in binary
  • Octal (Base 8): Prefixed with 0o
let octal = 0o377; // 255 in octal
  • Hexadecimal (Base 16): Prefixed with 0x
let hex = 0xFF; // 255 in hexadecimal

There are some special numeric representations, like Infinity and -Infinity, which represent values beyond the maximum representable number.

console.log(1 / 0);  // Infinity
console.log(-1 / 0); // -Infinity
console.log(Infinity + 1); // Infinity
console.log(Infinity); // Infinity
console.log(Infinity + 1); // Infinity
console.log(Math.pow(10, 1000)); // Infinity
console.log(Math.log(0)); // -Infinity
console.log(1 / Infinity); // 0
console.log(1 / 0); // Infinity

Another special representation is NaN (Not-a-Number), which represents an invalid number operation.

console.log("abc" * 3); // NaN
console.log(0 / 0); // NaN
console.log(NaN === NaN); // false (NaN is not equal to itself)

To check for NaN, use:

console.log(isNaN("abc")); // true
console.log(Number.isNaN(123)); // false (preferred, as it's stricter)

Number operations are an extensive subject, covered in a dedicated blog post.

Booleans

In JavaScript, a boolean is a fundamental data type that represents one of two values: true or false. Booleans are essential for controlling program flow through conditional statements, loops, and logical operations. They form the backbone of decision-making processes in programming.

let isJavaScriptFun = true;
let isSkyGreen = false;

console.log(isJavaScriptFun); // true
console.log(isSkyGreen); // false

You can directly assign true or false or obtain boolean results from comparisons and logical operations.

JavaScript can convert other data types to booleans. Use the Boolean() function to explicitly convert values to booleans.

console.log(Boolean(1));        // true
console.log(Boolean(0)); // false
console.log(Boolean("hello")); // true
console.log(Boolean("")); // false
console.log(Boolean(null)); // false
console.log(Boolean(undefined));// false

In JavaScript, all values are either “truthy” or “falsy” when evaluated in a boolean context. The following values are considered “falsy” (evaluate to false in boolean contexts):

  • false
  • 0 and -0
  • “” (empty string)
  • null
  • undefined
  • NaN

Everything else is “truthy”, including:

  • Non-zero numbers (1, -1, etc.)
  • Non-empty strings (“hello”, “0”, etc.)
  • Objects ({}, [])
  • Functions

Example:

if ("") {
console.log("Truthy!");
} else {
console.log("Falsy!"); // Output: "Falsy!"
}

if ([]) {
console.log("Truthy!"); // Output: "Truthy!" (empty arrays are truthy)
}

NOT (!) Inverts the boolean value: true becomes false and vice versa.

console.log(!true);  // false
console.log(!false); // true

let isAvailable = false;
console.log(!isAvailable); // true

Booleans are a fundamental part of JavaScript, enabling conditional logic, control flow, and decision-making. Understanding truthy/falsy values, logical operators, and boolean conversions is crucial for writing clean, efficient code. Whether you’re toggling UI states, validating user input, or controlling program logic, booleans are at the heart of every JavaScript application.

Null and Undefined

In JavaScript, few things are as deceptively simple yet confusing as null and undefined. They both represent the absence of a value, but in subtly different ways. Think of them as distant cousins: related, yet with distinct personalities and behaviors. Understanding when and why to use each is crucial to avoid bugs that lurk in the shadows of type coercion and equality checks.

Undefined Indicates that a variable has been declared but has not been assigned a value. It’s the default value for uninitialised variables and missing function arguments.

let x;
console.log(x); // undefined

Null Represents an intentional absence of any object value. It’s an assignment value, meaning a developer explicitly sets it to indicate “no value.”

let y = null;
console.log(y); // null

Understanding the nuances of null and undefined is like learning the difference between a missing chair and an empty chair. Both suggest “no one’s sitting,” but for entirely different reasons.

Data Structures

Data structures can store collections of values and more complex entities. They are used to manipulate related data in several ways.

Arrays

At its core, an array is a special kind of object designed to hold multiple values in a single, ordered collection. Imagine a row of mailboxes, each assigned a number starting from zero (because JavaScript has a fondness for zero-based indexing). Each mailbox can contain letters, packages, or even a small raccoon if you’re into exotic pets—similarly, JavaScript arrays can hold numbers, strings, objects, functions, or even other arrays.

There are several ways to create an array in JavaScript. Using square brackets is the most common way:

let fruits = ["Apple", "Banana", "Cherry"];
let numbers = new Array(1, 2, 3, 4, 5);
let emptyArray = [];
let fixedArray = new Array(10); // An array with 10 empty slots

Since arrays are zero-indexed, the first element lives at index 0, the second at 1, and so on.

let cars = ["Toyota", "Honda", "Ford"];
console.log(cars[0]); // Outputs: "Toyota"

cars[1] = "Tesla"; // Changing "Honda" to "Tesla"
console.log(cars); // ["Toyota", "Tesla", "Ford"]

If you try to access an index that doesn’t exist, JavaScript politely returns undefined instead of throwing a tantrum.

console.log(cars[5]); // undefined

Arrays are dynamic, meaning you can add or remove elements on the fly, push() adds to the end, unshift() adds to the beginning, pop() removes from the end and shift() removes from the beginning:

cars.push("Chevrolet");
console.log(cars); // ["Toyota", "Tesla", "Ford", "Chevrolet"]
cars.unshift("BMW");
console.log(cars); // ["BMW", "Toyota", "Tesla", "Ford", "Chevrolet"]
let lastCar = cars.pop();
console.log(lastCar); // "Chevrolet"
console.log(cars); // ["BMW", "Toyota", "Tesla", "Ford"]
let firstCar = cars.shift();
console.log(firstCar); // "BMW"
console.log(cars); // ["Toyota", "Tesla", "Ford"]

Need to organize data hierarchically? Arrays can contain other arrays.

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

console.log(matrix[1][2]); // Outputs: 6

Arrays are such an extensive and complex topic that they will be addressed again in a dedicated blog post.

Objects

An object is a collection of key-value pairs. The keys (also called properties) are strings (or symbols), and the values can be anything: numbers, strings, functions, arrays, or even other objects.

There are a couple of ways to create objects in JavaScript. Using object literals is the most common way:

let car = {
brand: "Tesla",
model: "Model 3",
year: 2022
};

Here, brand, model, and year are the keys, and “Tesla”, “Model 3”, and 2022 are their respective values.

You can access object properties in two ways: dot notation and bracket notation. Bracket notation is particularly useful when dealing with dynamic property names.

console.log(car.brand); // "Tesla"

console.log(car["model"]); // "Model 3"
let property = "year";
console.log(car[property]); // 2022

You can also add new properties or modify existing ones:

car.color = "red";           // Adding a new property
car.year = 2020; // Updating an existing property
delete car.model; // Removing a property

Objects can contain other objects, allowing you to model more complex data structures:

let rentalCar = {
brand: "Tesla",
model: "Model Y",
owner: {
name: "Alice",
license: "XYZ1234"
}
};

console.log(rentalCar.owner.name); // "Alice"

Objects can do more than just store data—they can also perform actions. As with other complex topics, object swill be a addressed again in their very own, dedicated blog post.

Sets

A Set in JavaScript is like an exclusive party—each value is allowed in only once. No duplicates, no exceptions. It’s a collection of values where uniqueness is the rule, not the exception.

Creating a Set is quite simple:

let uniqueNumbers = new Set([1, 2, 3, 4, 4, 5]);
console.log(uniqueNumbers); // Set(5) {1, 2, 3, 4, 5}

Notice how the duplicate 4 politely disappeared? That’s the magic of Set—it automatically filters out duplicates. You can add values using the add() method:

uniqueNumbers.add(6);
console.log(uniqueNumbers); // Set(6) {1, 2, 3, 4, 5, 6}

To remove a value, use delete():

uniqueNumbers.delete(3);
console.log(uniqueNumbers); // Set(5) {1, 2, 4, 5, 6}

Want to clear the entire set? Just call clear():

uniqueNumbers.clear();
console.log(uniqueNumbers); // Set(0) {}

Sets will also be addressed in another blog post.

Maps

A Map is like a turbocharged object. It lets you use any data type as a key—whether it’s a string, number, object, or even a function. It also remembers the order in which you add items, which makes iteration predictable and intuitive.

You can create a Map as follows:

let carMap = new Map();
carMap.set("brand", "Tesla");
carMap.set("model", "Model 3");
carMap.set("year", 2022);

console.log(carMap);
// Map(3) {"brand" => "Tesla", "model" => "Model 3", "year" => 2022}

Alternatively, you can initialise a Map with an array of key-value pairs:

let userMap = new Map([
["name", "Alice"],
["age", 30],
["isMember", true]
]);

console.log(userMap.get("name")); // "Alice"

Add an entry with set(key, value):

userMap.set("city", "New York");

Retrieve a value with get(key):

console.log(userMap.get("age")); // 30

Remove an entry with delete(key):

userMap.delete("city");

Clear all entries with clear():

userMap.clear();

Unlike objects, Map allows keys of any type:

let objKey = { id: 1 };
let map = new Map();
map.set(objKey, "Object as a key");

console.log(map.get(objKey)); // "Object as a key"

While objects are great for simple, static key-value data, Maps shine when:

  • You need keys of any data type.
  • The insertion order of items matters.
  • You perform frequent additions and deletions of key-value pairs (Maps are faster for these operations compared to objects).

The Map object in JavaScript offers flexibility and performance that objects simply can’t match for dynamic key-value data management. We will be seeing a lot more about maps in a different blog post.

WeakMap and WeakSet

Both WeakSet and WeakMap are specialised and offer a unique feature: they allow for weak references to objects. This means that the garbage collector can automatically remove these objects from memory when they’re no longer needed elsewhere in your code. In simpler terms, they help prevent memory leaks without you having to do any heavy lifting.

A WeakSet is similar to a regular Set, but with a twist: It can only contain objects—no primitive values like strings or numbers. The objects are held weakly, meaning if there are no other references to an object, it can be garbage collected automatically.

let obj1 = { name: "Alice" };
let obj2 = { name: "Bob" };

let weakSet = new WeakSet([obj1, obj2]);

console.log(weakSet.has(obj1)); // true

// Removing external references
obj1 = null; // The object { name: "Alice" } is now eligible for garbage collection

Since WeakSet doesn’t prevent garbage collection, you won’t find methods like size, clear(), or any way to iterate over its elements. It’s designed for specific use cases like tracking objects without worrying about memory leaks.

A WeakMap is like a regular Map, but with some key differences: Keys must be objects (no primitives allowed). Keys are held weakly, meaning if there are no other references to a key, it can be garbage collected along with its associated value.

let user = { id: 1 };
let weakMap = new WeakMap();

weakMap.set(user, "User data");

console.log(weakMap.get(user)); // "User data"

user = null; // The key-value pair is eligible for garbage collection

Just like WeakSet, WeakMap doesn’t support iteration methods (forEach, keys, values, etc.) because the keys can disappear at any moment when garbage collected.

While Set and Map are versatile, they can accidentally cause memory leaks if you forget to manually remove references. WeakSet and WeakMap solve this by design—they automatically let go of objects when they’re no longer needed. They are very specialised and you will probably only use them in very specific situations.

Conclusion

Understanding and leveraging JavaScript’s data structures, along with their real-world applications, is essential for crafting efficient and effective solutions. By matching the right data structure to your problem, you’ll unlock new levels of productivity and maintainability in your code.

Dive into your next project and see how these data structures can simplify your tasks! Happy coding!

Decoding Big O: Analysing Time and Space Complexity with Examples in C#, JavaScript, and Python


Efficiency matters. Whether you’re optimising a search algorithm, crafting a game engine, or designing a web application, understanding Big O notation is the key to writing scalable, performant code. Big O analysis helps you quantify how your code behaves as the size of the input grows, both in terms of time and space (meaning memory usage).


Big O notation was introduced by German mathematician Paul Bachmann in the late 19th century and later popularised by Edmund Landau. It was originally part of number theory and later adopted into computer science for algorithm analysis. Big O notation gets its name from the letter “O,” which stands for “Order” in mathematics. It is used to describe the order of growth of a function as the input size grows larger, specifically in terms of how the function scales and dominates other factors. The “Big” in Big O emphasises that we are describing the upper bound of growth. Big O notation describes the upper bound of an algorithm’s growth rate as a function of input size. It tells you how the runtime or memory usage scales, providing a worst-case scenario analysis.

Key Terminology:

  • Input Size (n): The size of the input data
  • Time Complexity: How the runtime grows with n
  • Space Complexity: How memory usage grows with

Common Big O Classifications

These are common complexities, from most efficient to least efficient:

Big O NameDescription
O(1)Constant ComplexityPerformance doesn’t depend on input size.
O(log n)Logarithmic ComplexityDivides the problem size with each step.
O(n)Linear ComplexityGrows proportionally with the input size.
O(n log n)Log-Linear ComplexityThe growth rate is proportional to n times the logarithm of n. It is often seen in divide-and-conquer algorithms that repeatedly divide a problem into smaller subproblems, solve them, and then combine the solutions
O(n2) or O(nk)Quadratic or Polynomial ComplexityNested loops—performance scales with n
O(2n)

Exponential Complexity

Grows exponentially—terrible for large inputs.

O(n!)Factorial ComplexityExplores all arrangements or sequences.

Analysing Time Complexity

Constant Time

In the first type of algorithm, regardless of input size, the execution time remains the same.

Example: C# (Accessing an Array Element)

int[] numbers = { 10, 20, 30, 40 };
Console.WriteLine(numbers[2]); // Output: 30

Accessing an element by index is O(1), as it requires a single memory lookup.

Logarithmic Time

The next most efficient case happens when the runtime grows logarithmically, typically in divide-and-conquer algorithms.

Example: JavaScript (Binary Search)

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
console.log(binarySearch([1, 2, 3, 4, 5], 3)); // Output: 2

Each iteration halves the search space, making this O(log n).

Linear Time

Example: Python (Iterating Over a List)

numbers = [1, 2, 3, 4, 5]
for num in numbers:
print(num)

The loop visits each element once, so the complexity is O(n).

Log-linear Time

This one takes a more elaborated and complex example. First, let’s break it down:

  • n : This represents the linear work required to handle the elements in each step
  • log n : This comes from the recursive division of the problem into smaller subproblems. For example, dividing an array into halves repeatedly results in a logarithmic number of divisions.

Example: JavaScript (Sorting arrays with Merge and Sort)

function mergeSort(arr) {
// Base case: An array with 1 or 0 elements is already sorted
if (arr.length <= 1) {
return arr;
}

// Divide the array into two halves
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);

// Recursively sort both halves and merge them
return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;

// Compare elements from left and right arrays, adding the smallest to the result
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}

// Add any remaining elements from the left and right arrays
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Example usage:
const array = [38, 27, 43, 3, 9, 82, 10];
console.log("Unsorted Array:", array);
const sortedArray = mergeSort(array);
console.log("Sorted Array:", sortedArray);

The array is repeatedly divided into halves until the subarrays contain a single element (base case), with complexity O(log n). The merge function combines two sorted arrays into a single sorted array by comparing elements (O(n)). This process is repeated as the recursive calls return, merging larger and larger sorted subarrays until the entire array is sorted.

Quadratic or Polynomial Time

In the simplest and obvious examples, nested loops lead to quadratic growth.

Example: C# (Finding Duplicate Pairs)

int[] numbers = { 1, 2, 3, 1 };
for (int i = 0; i < numbers.Length; i++) {
for (int j = i + 1; j < numbers.Length; j++) {
if (numbers[i] == numbers[j]) {
Console.WriteLine($"Duplicate: {numbers[i]}");
}
}
}

The outer loop runs n times, and for each iteration, the inner loop runs n-i-1 times. This results in O(n2).

Exponential Time

Generating all subsets (the power set) of a given set is a common example of exponential time complexity, as it involves exploring all combinations of a set’s elements.

Example: Python (Generating the Power Set)

def generate_subsets(nums):
def helper(index, current):
# Base case: if we've considered all elements
if index == len(nums):
result.append(current[:]) # Add a copy of the current subset
return

# Exclude the current element
helper(index + 1, current)

# Include the current element
current.append(nums[index])
helper(index + 1, current)
current.pop() # Backtrack to explore other combinations

result = []
helper(0, [])
return result

# Example usage
input_set = [1, 2, 3]
subsets = generate_subsets(input_set)

print("Power Set:")
for subset in subsets:
print(subset)

For a set of n elements, there are 2n subsets. Each subset corresponds to a unique path in the recursion tree. Therefore, the time complexity is O(2n

Factorial Time

These algorithms typically involve problems where all possible permutations, combinations, or arrangements of a set are considered.

Example: Javascript (Generating All Permutations)

function generatePermutations(arr) {
const result = [];

function permute(current, remaining) {
if (remaining.length === 0) {
result.push([...current]); // Store the complete permutation
return;
}

for (let i = 0; i < remaining.length; i++) {
const next = [...current, remaining[i]]; // Add the current element
const rest = remaining.slice(0, i).concat(remaining.slice(i + 1)); // Remove the used element
permute(next, rest); // Recurse
}
}

permute([], arr);
return result;
}

// Example usage
const input = [1, 2, 3];
const permutations = generatePermutations(input);

console.log("Permutations:");
permutations.forEach((p) => console.log(p));

For n elements, the algorithm explores all possible arrangements, leading to n! recursive calls.

Analysing Space Complexity

Space complexity evaluates how much additional memory an algorithm requires as it grows.

Constant Space

An algorithm that uses the same amount of memory, regardless of the input size.

Example: Python (Finding the Maximum in an Array)

def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val

Only a fixed amount of memory is needed, regardless of the size of or n.

Logarithmic Space

Typically found in recursive algorithms that reduce the input size by a factor (e.g., dividing by 2) at each step. Memory usage grows slowly as the input size increases

Example: C# (Recursive Binary Search)

static void SearchIn(int target, string[] args)
{
int[] array = { 1, 3, 5, 7, 9, 11 };
int result = BinarySearch(array, target, 0, array.Length - 1);
if (result != -1)
{
Console.WriteLine($"Target {target} found at index {result}.");
}
else
{
Console.WriteLine($"Target {target} not found.");
}
}

static int BinarySearch(int[] arr, int target, int low, int high)
{
// Base case: target not found
if (low > high)
{
return -1;
}
// Find the middle index
int mid = (low + high) / 2;
// Check if the target is at the midpoint
if (arr[mid] == target)
{
return mid;
}
// If the target is smaller, search in the left half
else if (arr[mid] > target)
{
return BinarySearch(arr, target, low, mid - 1);
}
// If the target is larger, search in the right half
else
{
return BinarySearch(arr, target, mid + 1, high);
}
}

Binary Search halves the search space at each step. The total space usage grows logarithmically with the depth of recursion, resulting in  O(log n).

Linear Space

Memory usage grows proportionally with the input size.

Example: JavaScript (Reversing an Array)

function reverseArray(arr) {
let reversed = [];
for (let i = arr.length - 1; i >= 0; i--) {
reversed.push(arr[i]);
}
return reversed;
}

console.log(reverseArray([1, 2, 3])); // Output: [3, 2, 1]

The new reversed array requires space proportional to the input size.

Log-linear space complexity algorithm

This type of algorithm requires memory proportional to n log n, often due to operations that recursively split the input into smaller parts while using additional memory to store intermediate results.

Example: Python (Merge Sort)

def merge_sort(arr):
if len(arr) > 1:
# Find the middle point
mid = len(arr) // 2

# Split the array into two halves
left_half = arr[:mid]
right_half = arr[mid:]

# Recursively sort both halves
merge_sort(left_half)
merge_sort(right_half)

# Merge the sorted halves
merge(arr, left_half, right_half)

def merge(arr, left_half, right_half):
i = j = k = 0

# Merge elements from left_half and right_half into arr
while i < len(left_half) and j < len(right_half):
if left_half[i] <= right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1

# Copy any remaining elements from left_half
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1

# Copy any remaining elements from right_half
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1

# Example usage
if __name__ == "__main__":
array = [38, 27, 43, 3, 9, 82, 10]
print("Unsorted Array:", array)
merge_sort(array)
print("Sorted Array:", array)

The depth of recursion corresponds to the number of times the array is halved. For an array of size n, the recursion depth is log n. At each level, temporary arrays (left_half and right_half) are created for merging, requiring O(n) space. The total space complexity is given by
O(log n) recursion stack + O(n) temporary arrays = O(n log n).

Quadratic or Polynomial Space

This case encompasses algorithms that require memory proportional to the square or another polynomial function of the input size.

Example: Python (Longest Common Subsequence)

def longest_common_subsequence(s1, s2):
n, m = len(s1), len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]

This algorithm requires a two dimensions table storing solutions for all substrings, therefore the space complexity is O(nk).

Exponential Space

An algorithm with exponential space complexity typically consumes memory that grows exponentially with the input size. 

Example: Javascript (Generating the Power Set)

function generatePowerSet(inputSet) {
function helper(index, currentSubset) {
if (index === inputSet.length) {
// Store a copy of the current subset
powerSet.push([...currentSubset]);
return;
}
// Exclude the current element
helper(index + 1, currentSubset);

// Include the current element
currentSubset.push(inputSet[index]);
helper(index + 1, currentSubset);
currentSubset.pop(); // Backtrack
}
const powerSet = [];
helper(0, []);
return powerSet;
}

// Example usage
const inputSet = [1, 2, 3];
const result = generatePowerSet(inputSet);

console.log("Power Set:");
console.log(result);

The recursion stack consumes O(n) space (depth of recursion). The memory for storing the power set is O(2n), which dominates the overall space complexity.

Factorial Space

These are algorithms found in problems that involve generating all permutations of a set.

Example: C# (Generating All Permutations)

static void Main(string[] args)
{
var input = new List<int> { 1, 2, 3 };
var permutations = GeneratePermutations(input);
Console.WriteLine("Permutations:");
foreach (var permutation in permutations)
{
Console.WriteLine(string.Join(", ", permutation));
}
}

static List<List<int>> GeneratePermutations(List<int> nums)
{
var result = new List<List<int>>();
Permute(nums, 0, result);
return result;
}

static void Permute(List<int> nums, int start, List<List<int>> result)
{
if (start == nums.Count)
{
// Add a copy of the current permutation to the result
result.Add(new List<int>(nums));
return;
}
for (int i = start; i < nums.Count; i++)
{
Swap(nums, start, i);
Permute(nums, start + 1, result);
Swap(nums, start, i); // Backtrack
}
}

static void Swap(List<int> nums, int i, int j)
{
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

The algorithm generates n! permutations, and each permutation is stored in the result list. For n elements, this requires O(n!) memory.

Wrapping It Up

Big O notation is a cornerstone of writing efficient, scalable algorithms. By analysing time and space complexity, you gain insights into how your code behaves and identify opportunities for optimisation. Whether you’re a seasoned developer or just starting, mastering Big O equips you to write smarter, faster, and leaner code.

With this knowledge in your arsenal, you’re ready to tackle algorithm design and optimisation challenges with confidence.