Time vs Space Complexity
Time complexity counts steps. Space complexity counts memory. Both say how the cost grows as the input grows, and a faster way often needs more memory.
Time Complexity
How much more work as the input grows. It is written in Big O.
Time complexity is how the number of steps an algorithm takes grows with the size of its input. It is written in Big O, like O(n) or O(n log n). It counts steps rather than seconds, so it does not depend on how fast the computer is. Looking up a key in a hash table is O(1) on average. Sorting with merge sort is O(n log n).
Space Complexity
How much extra memory a task needs. It grows with the input.
Space complexity is how much extra memory an algorithm needs as its input grows. Like time complexity, it is written in Big O. Sorting a list in place may need O(1) extra memory. Making a full copy of the list needs O(n). Often you can trade one for the other: use more memory to save time, or the reverse.
In one line
- Time Complexity
- How much more work as the input grows. It is written in Big O.
- Space Complexity
- How much extra memory a task needs. It grows with the input.