Time complexity and space complexity are two ways of evaluating the efficiency of an algorithm. However, they measure two fundamentally different things.
**Time Complexity**
Time complexity is a measure of the total time required by an algorithm to complete its execution. In other words, it measures the amount of computer time that an algorithm needs to process input data of a given size.
We typically express time complexity using Big O notation. This notation provides a high-level analysis of the algorithm’s efficiency by describing the worst-case scenario, i.e., the maximum time needed for execution as the size of the input data approaches infinity.
For example, consider an algorithm that checks whether a number is prime by dividing it by every number up to its square root. The time complexity would be O(sqrt(n)), where n is the number being checked, because the algorithm’s time requirement increases in proportion to the square root of the size of the input data.
**Space Complexity**
Space complexity, on the other hand, measures the amount of memory an algorithm needs to execute. It includes both the space required to hold the input data as well as any additional space the algorithm might require to hold intermediate results or output data.
Just like time complexity, space complexity is often expressed using Big O notation to represent the worst-case scenario.
For instance, consider an algorithm that generates all permutations of a given string. Since it needs to store all permutations at once, it requires an amount of space proportional to the factorial of the length of the string. Therefore, its space complexity would be O(n!), where n is the length of the string.
**Time-Space Trade-off**
In many cases, there’s a trade-off between time and space complexity. That is, you can often make an algorithm run faster by having it use more memory (a lookup table, for example), or make an algorithm use less memory by having it take more time.
Here is a small table chart to show the common complexities:
| Big O Notation | Name |
| ------------- |:-------------:|
| O(1) | Constant |
| O(log n) | Logarithmic |
| O(n) | Linear |
| O(n log n) | Linear Logarithmic |
| O($n^2$) | Quadratic |
| O($n^3$) | Cubic |
| O($2^n$) | Exponential |
| O(n!) | Factorial |It is worth mentioning that when analyzing an algorithm, understanding time and space complexity is important not just to quantify the total time or space an algorithm uses, but to understand how those quantities change as the size of the input data changes.