Calculating Time Complexity and Space Complexity

It might be seems not important, but we have to understand the way it works so we can be a better programmer.

In calculating time complexity and space complexity (which is usually denoted by Big-O notation), there are several rules that need to be followed here:

• Ignore constant, for example O(N + 2), we can consider it as O(N).
• Ignore non dominant terms, for example O(N² + N), we can consider it as O(N²).

Time Complexity

Time complexity is the amount of time taken by an algorithm to run, as a function of the length of the input. It measures the time taken to execute each statement of code in an algorithm.

First Example

function add(x: number, y: number): number {
  return x + y;
}

The time complexity of function above is O(1), because no matter what number from parameter (input), it always running instruction once.

What about this function? (contain for loop)

function double(numbers: number[]): number {
    var sum:number = 0;
    for (const number of numbers) {
        sum += number;
    }
    return sum / numbers.length;
}

The time complexity of function double is O(n) because the number of loops depends on the length of the array passed to the function.

What about this function? (contain nested for loop)

function(n: number): number {
    var count:number = 0;
    for (let i = 0; i <= n; i++) {
       for (let j = 0; j <= i; j++) {
           count++;
       }  
    }
    return count;
}

How many times count++ running with any value of n?

• if i = 1, then it will run once.
• if i = 2, then it will run twice.
• if i = 3, then it will run three times.
• and so on..

So count++ will run…

The time complexity will be O(n²), remember about the rules that I told you earlier.

Now let’s try with a little more line of code (contain 3 for loop).

someFunction function(a: number[], b: number[]): number {
    var x:number = 0;
    var y:number = 1;
    for (let i = 0; i < a.length; i++){
        x += a[i];
    }
    for (let j = 0; j < b.length; j++){
        y *= b[j];
    }
    for (let k = 0; k < 10; k++){
        y += 1;
        x -= 1;
    }
 
    return x + y;
}

Let’s say length of array a is N and length of array b is M , time complexity can be determine like this:

Hold on, looping for (let k = 0; k < 10; k++) ‘s complexity is O(1) because it will be running 10 (constant) times.

So the time complexity of someFunction is O(N+M) or if we determine length of both array a and b are N, it will be O(2N).

Space Complexity

Space complexity refers to the total amount of memory space used by an algorithm/program, including the space of input values for execution.

For example

function add(x: number, y: number): number {
    return x + y;
}

This function need 2 unit of space (2 parameter x and y), when this function is running, this memory space allocation will remain, regardless of the input, so the space complexity is O(1).

Second

function double(numbers: number[]): number {
    var sum:number = 0;
    for (const number of numbers) {
        sum += number;
    }
    return sum / numbers.length;
}

This function need N unit of space (any number of parameter numbers) and 1 unit of space for variable sum. The space complexity is O(n), because this function will require at least N units of space in memory, depending the length of array.

In conclusion

Time Complexity determine how long an algorithm runs at runtime based on the given input, Space Complexity determine how much space in memory an algorithm takes up at runtime.

Source:
https://medium.com/99ridho/mengenal-dan-menghitung-time-complexity-dan-space-complexity-6418ea767336
https://www.simplilearn.com/tutorials/data-structure-tutorial/time-and-space-complexity