(Elements of programming interviews 12.5.)
One way of improving time complexity at the expense of space complexity is to use a cache.
If a programme makes multiple passes over the same data or calls to the same function a cache might be useful.
We avoid redundant computations because the results to previous work can be accessed in
For instance consider the problem:-
A brute-force approach might be to find – for each element of the array – the next element of the array equal to it. So a carefree solution might be the following:
O(n^2) time complexity and
O(1) space complexity.
Notice also that we are making multiple passes over the data.
A cache improves the time complexity because it makes the outer loop redundant. We don’t have to iterate through the array for each element but only keep track of the most recent occurrence of each element. This could look like:
which has time complexity
O(n) space complexity.