Understanding Big-O Notation with Real-World Examples

Big-O is a way to describe how the runtime or memory usage of an algorithm grows as the input size increases.

First, time complexity :
Suppose I have a task like finding a book in a library. If the books are unsorted, I might have to check each one until I find the right one. That's like linear time, O(n), because in the worst case, I check every single book. If the books are sorted, maybe I can use a binary search approach, which is O(log n), because I keep dividing the remaining books in half. That makes sense—each step reduces the problem size by half.

Now space complexity:
Suppose I'm moving to a new apartment and need to pack my books. If I have a shelf that holds n books, the space required is O(n). But if I decide to create a matrix of connections between friends for a social network, that could be O(n²) space if I store every possible connection. If I use a more efficient structure like an adjacency list, maybe it's O(n + m) where m is the number of connections. That's a way to optimize space.

Let's dive deeper into each time and space complexity with example code.

Time Complexity: How Runtime Grows with Input Size

• O(1) – Constant Time

  • Example: Turning on a lamp.

    • No matter how many bulbs are in your house, flipping a specific switch takes the same time.

  • Code Example: Accessing an array element by index (arr[5]).

    const arr = [10, 20, 30, 40, 50]; 

    // Accessing an element by index (constant time operation)
    const element = arr[2]; // Retrieves 30

    console.log(element); // Output: 30

• O(n) – Linear Time

  • Example: Finding a book in an unsorted library.

    • If the library has n books, you might check each one in the worst case.

  • Code Example: Linear search (looping through an array).

    function linearSearch(arr, target) {
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] === target) {
                return i; // Return the index of the found element
            }
        }
        return -1; // Return -1 if the element is not found
    }

    const books = ["Harry Potter", "Lord of the Rings", "The Hobbit", "Dune"];
    const targetBook = "The Hobbit";

    const index = linearSearch(books, targetBook);

    console.log(index !== -1 ? `Book found at index ${index}` : "Book not found");

• Explanation:

  • The function loops through the array, checking each element.

  • In the worst case, it may have to check all n elements, making it O(n).

  • The more elements in the array, the longer it takes.

O(log n) – Logarithmic Time

• Example: Looking up a word in a dictionary.

  • You split the dictionary in half repeatedly, eliminating half the words each time.

• Code Example: Binary search (works on sorted arrays).

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

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (arr[mid] === target) return mid;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    };

    const words = ["apple", "banana", "cherry", "date", "elderberry", "fig", "grape"];
    const targetWord = "cherry";

    console.log(binarySearch(words, targetWord));

Explanation:

• The function repeatedly splits the array in half by adjusting the left and right pointers.

• Each iteration reduces the problem size by half, leading to logarithmic time complexity, O(logn).

• This approach works only on sorted arrays.

O(n²) – Quadratic Time

• Example: Handshakes at a party.

  • If n people attend, each person shakes hands with n-1 others. Total handshakes ≈ n²/2.

• Code Example: Nested loops (e.g., Bubble Sort).

    const bubbleSort = (arr) => {
        const n = arr.length;
        for (let i = 0; i < n - 1; i++) {
            for (let j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap elements
                    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                }
            }
        }
        return arr;
    };
  
    const numbers = [5, 3, 8, 4, 2];
    console.log(bubbleSort(numbers));
  

  Explanation:

  • Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements and swapping them if necessary.

  • The outer loop runs nnn times, and for each iteration, the inner loop also runs up to nnn times.

  • This results in quadratic time complexity, O(n^2), because of the two nested loops.

O(2ⁿ) – Exponential Time

• Example: Generating all possible passwords of length n.

  • Each character added doubles the combinations (e.g., 2ⁿ for binary passwords).

• Code Example: Recursive Fibonacci (without memoization).

    const fibonacci = (n) => {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    };
  
    const result = fibonacci(5);
    console.log(result); // Output: 5
  

Explanation:

• The Fibonacci function calls itself twice for each value of nnn, except for the base cases (0 and 1).

• Each call creates two more calls, leading to an exponential growth in the number of function calls.

• This results in exponential time complexity O(2n), as the number of calls doubles with each increment in n.

2. Space Complexity: How Memory Usage Grows with Input Size

O(1) – Constant Space

• Example: Using a single notebook for calculations.

  • You only need a fixed amount of space, regardless of the problem size.

• Code Example: Swapping two variables (a, b = b, a).

    let a = 5;
    let b = 10;

    // Swapping using a temporary variable
    [a, b] = [b, a];

    console.log(a, b); // Output: 10 5

Explanation:

• In this example, the space required to swap the two variables remains constant, regardless of the values of a and b.

• The space complexity is O(1) because only a fixed amount of space (for the variables) is needed, no matter the input size.

O(n) – Linear Space

• Example: Storing a list of groceries.

  • A list of n items requires space proportional to n.

• Code Example: Storing an array or a hash table.

    const groceries = ["apple", "banana", "carrot", "lettuce", "tomato"];

    console.log(groceries); // Output: ["apple", "banana", "carrot", "lettuce", "tomato"]

Explanation:

• The space required to store the list of groceries grows linearly with the number of items in the list.

• If the list has nnn items, the space used is proportional to nnn, making it O(n) space complexity.

• The more groceries you add, the more space the array will require.

O(n²) – Quadratic Space

• Example: A chessboard with n pieces.

  • Storing all possible pairs of piece positions would take n² space.

• Code Example: A 2D matrix (e.g., adjacency matrix for a graph).

    const createAdjacencyMatrix = (n) => {
        const matrix = Array.from({ length: n }, () => Array(n).fill(0)); // Creating an n x n matrix

        // Example: Adding some edges to the matrix
        matrix[0][1] = 1; // Edge from node 0 to node 1
        matrix[1][2] = 1; // Edge from node 1 to node 2
        matrix[2][0] = 1; // Edge from node 2 to node 0

        return matrix;
    };

    const n = 3;
    const adjacencyMatrix = createAdjacencyMatrix(n);
    console.log(adjacencyMatrix);

Explanation:

• In this example, we create an n×n matrix to represent an adjacency matrix for a graph, where n is the number of nodes.

• The space used by the matrix grows quadratically with n, resulting in O(n^2) space complexity.

• The matrix stores all possible pairs of node connections (edges), so if there are n nodes, the matrix requires space proportional to n^2

Let's consider another real-world analogy for Big-O.

Imagine you’re a delivery driver optimizing routes:

• O(1): A fixed route that never changes, regardless of packages.

• O(n): Driving to each house one by one.

• O(n²): Checking every possible route combination between n houses.

• O(log n): Using a GPS that halves the remaining options each turn.