Big O Insights(deriveit.org)
deriveit.org
Big O Insights
https://deriveit.org/coding/cheat-sheets/big-o-insights-106?h=t
1 comments
Agreed. Was working on a parallel algo whose width could grow exponentially. It was clear that it made more sense to analyze from a space perspective.
I don't think the claim is true in quite as much generality as the author claims. Some deterministic data structures use much more space than time, for example, the deterministic implementation of a Van Emde Boas tree.
I think you're missing out on the time it takes to build the tree in the first place, which is O(M), equal the space complexity. People usually ignore this cost as a "preprocessing" factor, but it's a cost that's really there.
After this initial O(M) time and space cost, you do additional operations which only take up time, not space, so the claim Time >= Space holds here as well.
After this initial O(M) time and space cost, you do additional operations which only take up time, not space, so the claim Time >= Space holds here as well.
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.
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.
> This is why you usually assume infinite memory in most problems, and why I consider limited-memory problems like in-place sorting to not be very interesting. Time limits space, so time is more interesting.
Yeah, I'm not sure I agree with this statement. Citation needed.