Space complexity is always less than time complexity. If every operation can only access a constant number of memory spaces, something in O(f) can only touch O(f*k) memory spaces. Thus, space complexity is bounded by time complexity. (I don't know why I ended with a formula kinda swearing at me, but I'll leave it because it make me chuckle immaturely).
The inverse however has very few implications. You don't need much space to get into huge time complexities. Something like prime factorization has very little space requirements, but becomes very time-expensive very quickly.
Though I'm kind of disappointed that this article doesn't touch on the practically weird parts of complexity theory. For example how at times, the asymptotically better algorithm isn't used in practive, because the preprocessing only barely starts to break even with an asymptotically worse algorithm at input sizes of millions and billions, while practical problems are at input sizes of 10k - 100k.
Comments
Space complexity is always less than time complexity. If every operation can only access a constant number of memory spaces, something in O(f) can only touch O(f*k) memory spaces. Thus, space complexity is bounded by time complexity. (I don't know why I ended with a formula kinda swearing at me, but I'll leave it because it make me chuckle immaturely).
The inverse however has very few implications. You don't need much space to get into huge time complexities. Something like prime factorization has very little space requirements, but becomes very time-expensive very quickly.
Though I'm kind of disappointed that this article doesn't touch on the practically weird parts of complexity theory. For example how at times, the asymptotically better algorithm isn't used in practive, because the preprocessing only barely starts to break even with an asymptotically worse algorithm at input sizes of millions and billions, while practical problems are at input sizes of 10k - 100k.