The Complete Guide To Understanding Time and Space Complexity of Algorithms

This topic is super trendy in interviews, so you should know it if you are looking for a job

Image by the author

There’s more than one way to solve a problem, but not all of them are the best. Not every solution is capable of efficiently using our resources. Therefore we need to find the best, most efficient solution to a problem before taking action.

In programming, we can’t leave the mechanism of finding the best solution, the best algorithm, to guesswork. We need a clear standard to evaluate the efficiency of solutions. This is where the concepts of time and space complexity step in. They help us determine the algorithm’s efficiency based on the required resources.

In this article, we are going to talk about the concepts of time and space complexity and how we can use them to select the most efficient algorithm for a given task. And of course, this is where notations like O(n) and O(logn), which may have baffled you while learning algorithms, come from.

Efficiency of Algorithms

We measure an algorithm’s efficiency using the time and space (memory) it takes for execution. Time is important because we need our programs to run as fast as possible to deliver the results quickly. Space is important because machines have only a limited amount of space to spare for programs.

The best algorithm is the one that completes its execution in the least amount of time using the least amount of space. But often, in reality, algorithms have to trade off between saving space or time.

That’s why the best algorithm for a given task is not something that’s fixed in stone. The best algorithm depends on our requirements. If we need our algorithm to run as fast as possible despite the memory usage, we can pick the most time-efficient algorithm as the best algorithm, and vice versa.

And if we need to save both time and space, we can settle for an algorithm that uses average amounts of time and space.

Space Complexity

Space complexity of an algorithm is the amount of space it uses for execution in relation to the size of the…