undefined | Better HN

0 pointsdgfitz1y ago0 comments

I opened the link and just started reading. I have a really dumb question that may expose common knowledge I don’t have, about this quote:

> The total amount of space needed to represent this collection of strings is O(k n^2).

I haven’t seen O-notation ever represent ram usage, just algorithm complexity. Is this common?

0 comments

nneonneo1y ago

Yes, very common. You've seen "time complexity"; it's very common to talk about "space complexity" as well.

consp1y ago

Fun bonus: they can be interchangeable, e.g. increasing space to reduce time.

asboans1y ago

And any operation that takes n bits as input can be trivially turned into an O(1) time and O(2^n) space algorithm through tabulation.

1 more reply

dgoldstein01y ago

Yes, but total time is never going to be less than total space, when expressed in big-O notation

2 more replies

masklinn1y ago

> Is this common?

Very. For instance if you look at sorting algorithms on wikipedia they pretty much all list performance (best, worst, average) but also worst-case space complexity, in O notation.

j / k navigate · click thread line to collapse