Time & Space Complexity

Analysis of the algorithm is the process of analyzing the problem-solving capability of the algorithm in terms of the time and size required (the size of memory for storage while implementation).

However, the main concern of the analysis of algorithms is the required time or performance
Generally, we perform the following types of analysis −

• Worst-case − The maximum number of steps taken on any instance of size a.
• Best-case − The minimum number of steps taken on any instance of size a.
• Average case − An average number of steps taken on any instance of size a.
• Amortized − A sequence of operations applied to the input of size a averaged over time.

Time complexity

It is a concept used in computer science to describe the amount of time an algorithm takes to run as a function of the length of the input. It is a measure of how the execution time of an algorithm grows relative to the size of the input. Time complexity is typically expressed using big O notation, which provides an upper bound on the growth rate of the running time as the input size increases.

In simple terms, time complexity helps us understand how efficient an algorithm is in terms of the time it takes to solve a problem as the input size grows larger. It doesn't measure the actual time in seconds but gives us a sense of how the algorithm's performance scales with input size.

Consider this example

To check whether a number is Prime or not?

Method 1

function isPrime(n) {
 for (let i = 2; i < n; ++i) {
    if (n % i === 0) {x`
        return false;
    }
 }
 return true;
}

Here the loop will run n-2 times

Method 2

function isPrime(n) {
  for (let i = 2; i <= Math.sqrt(n); ++i) {
      if (n % i === 0) {
          return false;
      }
  }
  return true;
}

Here the loop will run √n​-2 times

Conclusion

The second method is faster. That’s why time complexity is important. In real life we want softwares to be fast & smooth.

How to calculate time complexity?

code 1

for (let i = 0; i < n; ++i) {

    console.log(i);

}

Here the loop will run n times

Time Complexity: O(n)

code 2

for (let i = 0; i < n; ++i) {

    for (let j = 0; j < n; ++j) {

        console.log(i, j);

    }

}

Here the loop will run n² times

Time Complexity: O(n²)

What is space complexity?

In computer science, the space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of the size of the input.

In simple words,
Space complexity of a program is a simple measurement of how fast the space taken by a program grows, if the input increases.

How to calculate space complexity

General rules

The space taken by variable declaration is fixed(constant), 

like:  let i = 0;
This space requirement is constant and is considered as Big O of 1 i.e., O(1)
Our focus is more on the non-constant space requirement, which grows with input size.

How to calculate space complexity?

code 1

const arr = [];

for (let i = 0; i < n; ++i) {

    arr.push(i);

}

Here the array will take n space

Space Complexity: O(n)

code 2

const arr = [];

for (let i = 0; i < n; ++i) {

    for (let j = 0; j < n; ++j) {

        arr.push(i + j);

    }

}

Here the array will take n² space

Space Complexity: O(n²)