Adil Ismail

Understanding Time and Space Complexity in Algorithms

Time and space complexity are used to analyze the performance of an algorithm.

Time complexity

It is used to measure the amount of time an algorithm takes to run. It helps us understand how the algorithm's runtime grows with the increase in input size. In the real world performance of an algorithm will depend on the CPU, memory etc, however we don't consider these factors while analysing the algorithm. Time complexity is usually expressed in Big O notation in the industry, Big O describes the worst-case scenario for how the algorithm's time requirement increases as the size of the input data grows.

Some common Big O notations:

O(1) Constant time complexity

O(1) is constant time, that is even if the input is small or large the function will take the same amount of time to complete.

In the below example even if the input array is very large or small the function will complete in same amount of time.

    function appendToArray(arr, value) {
        return arr.push(value)
    }

Another example of O(1):

    function sum(a, b) {
        const sum = a+b;
        return sum;
    }

O(n) Linear time complexity

In Big O(n) as the input size grows the time complexity also grows linearly. Consider the below example as the input size n increases(5->500), the time taken to execute the algorithm also increases linearly. We have a 2 statements in the below code, the first statement divides 1/2 even if n is a large number or a small number this statement will execute in the same time. The second statement is a loop, when the input n changes the loop iterations also change depending on the input. We can say the loop is executing n times so the time complexity for this statement is O(n). So the final time complexity of the function print will be O(n) because it is the biggest, and we ignore the smaller one O(1).

    function print(n) {
        const constantTimeOperation = 1/2;
        for (let i=0; i< n; i++) {
            console.log(n)
        }
    }

O(n^2) Quadratic time complexity

It means that the time taken to execute the algorithm grows quadratically, for example, if the input size doubles, the time taken to execute the algorithm increases fourfold.

function quadraticAlgorithm(arr) {
    let result = 0;
    for (let i = 0; i < arr.length; i++) {        // Outer loop runs 'n' times
        for (let j = 0; j < arr.length; j++) {    // Inner loop also runs 'n' times for each iteration of the outer loop
            result += arr[i] * arr[j];             // Some operation
        }
    }
    return result;
}

O(log n) Logarithmic time complexity

Logarithmic time complexity indicates that the time taken by an algorithm increases logarithmically as the size of the input increases. The algorithm's performance improves with each doubling of the input size, a common example is binary search.

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;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } 
        else {
            right = mid - 1;
        }
    }
    return -1;
}

Binary search divides the search interval in half at each step, effectively reducing the search space by half with each comparison. Logarithmic time complexity is highly efficient for large datasets compared to linear or quadratic time complexities.

Space complexity

Space complexity refers to the amount of memory required by an algorithm to run as a function of the input size. Similar to time complexity, space complexity is also expressed using Big O notation.

O(1) Constant space complexity

Algorithm with O(1) space complexity take up a fixed amount of memory regardless of the input size. In the below function name is the only defined variable, even if the input size grows massively it wont effect the memory footprint.

    function print(n) {
        const name = 'hello';
        for (let i=0; i< n; i++) {
            console.log(n)
        }
        return name
    }

O(n) Linear space complexity

An algorithm with O(n) space complexity will increase the memory footprint linearly. In the below example we are looping n times and pushing to an array, so when the input size grows resArr will also grow so this is a O(n) space complexity algorithm.

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

O(n^2) Quadratic space complexity

Quadratic space complexity refers to an algorithm whose memory usage grows quadratically with the size of the input. In other words if the input size increases by a factor of n, the memory usage of the algorithm increases by a factor of n^2.

function generateSquareMatrix(n) {
    const matrix = [];
    for (let i = 0; i < n; i++) {
        matrix[i] = [];
        for (let j = 0; j < n; j++) {
            matrix[i][j] = i * n + j; // Fill matrix with unique values
        }
    }
    return matrix;
}

Consider the above example, generateSquareMatrix is used to create a matrix of size n*n. As the input n grows so does the matrix array by a factor of n^2.

← Back to home