I've been studying some sorting algorithms and have come across some inverse relationships between time and space complexity. For example, an algorithm like selection sort takes O(n^2) but only requires constant space as it can be done in place. An algorithm like merge sort however has O(nlogn) time complexity but requires O(n) space.
My questions are
Is there a theorem or law that relates time and space complexity trade offs to one another? Is this phenomenon only present is sorting algorithms or does this trade off also persist in other problems?
Is it always a good idea to trade space complexity for time complexity with a huge increase in modern RAM sizes? Or is there times when decreasing the time complexity would make the space complexity prohibitively large.
On answer to your first question - no there is not any. This comes from the case by case analysis of an algorithm. There is no mathematical formula that will calculate the space - time complexity trade-off. And yes it persists in other algorithms too. For example: consider the problem of getting running sum in an array - with updates in between. If you store in O(n) memory (array) then the complexity would be O(n) for retrieving specific sum over a range in the array. But if you keep a segment tree with O(4*n)~O(n) space complexity it would give O(logn) update and retrieval.
No it is not. Having huge space complexity won't compensate for the extra memory that we earn today. The performance will be constrained by memory access etc.
Some cases the decrease in time complexity can only be achieved with relatively high space complexity. For example, If data is stored is uncompressed, it takes more space but access time is smaller than if the data were stored compressed (since compressing the data reduces the amount of space it takes, but it takes some time to run the decompression algorithm). It is depending upon the scenario that we will face and that dictates which solution we want to go for.