Time And Space Complexity

By Annesha Mukhopadhyay

Why Do We Care About Complexity

If you are someone who has been writing codes for quite some time now, you are bound to have heard of time and space complexity. But why are they important? To understand that, we first need to understand what time and space complexity are.

Time Complexity

Time Complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input.

Time Complexity is an umbrella term for the different types of time complexities we can calculate which includes:

• Worst Case Time Complexity: This is the maximum number of times an operation needs to be executed before the algorithm is completed

• Average Case Time Complexity: This is the average number of times an operation needs to be executed before the code is completed

• Best Case Time Complexity: This is the least number of time an operation needs to be completed

We should keep in mind that time complexity is not the actual amount of time taken by the machine on which the algorithm is running.

Space Complexity

Space complexity is basically the total space used by an algorithm with respect to the input size. It includes both auxiliary space (i.e., the temporary space used during the execution of an algorithm) and the space used by the input.

It is important to remember that space complexity depends on a variety of factors like the programming language used, the compiler or even the machine running the algorithm.

In simpler terms, given the size of the input, the number of steps the algorithm will need to perform to be completed is the time complexity and the amount of storage the algorithm requires while working, I.e., performing all those steps is the space complexity.

Why do time and space complexity matter?

In a real world scenario, programmers and developers are bound by the physical constraints of the device they intend to run their applications on and this is where time and space complexity become important. We don’t want an algorithm that exceeds the amount of usable space a system has at any given point. At the same time, we also don’t want the algorithm to take so long that the application gets slowed down.

Neither of the two are more important than the other and the key to writing efficient codes is finding the balance between the two. Since space is reusable it is sometimes smarter to use more space to speed up the algorithm. But at the same time using too much space will eventually slow down the application because the total amount of space is fixed for any hardware. So, your algorithms should not have a very high time complexity but should also not have an absurdly high space complexity.

~Mijo