Talk:DSPACE

Expand to an article about space complexity?

It seems this is currently the main article about space complexity, since David Eppstein redirected that page here. Does it make sense to expand and rename this article to cover space complexity in general? QVVERTYVS (hm?) 13:27, 12 January 2015 (UTC)

I wasn't the one to make that title into a redirect; that happened back in 2006. I merely changed the redirect to point to something that was actually about space complexity. But if you want to change the redirect back into an overview of space complexity more generally, that would make more sense to me than giving up on the existence of an article on DSPACE specifically. But is there more to do than just pointing to our DSPACE and NSPACE articles? In that case even a set index article seems unnecessary. —David Eppstein (talk) 17:08, 12 January 2015 (UTC)

I think WP can use a less formal overview of space complexity, perhaps with some more discussion from the viewpoint of the analysis of algorithms. I noticed many algorithm articles link here, and the jump from practical algorithms to Turing machines is quite big for those not familiar with theoretical CS. I'll have a stab at it. QVVERTYVS (hm?) 19:52, 12 January 2015 (UTC)

DSPACE(O(f)) vs DSPACE(f)

In most definitions (e.g. Michael Sipser, or this article), DSPACE(f) is the class of languages decidable in O(f). So it is superfluous to write DSPACE(O(f)) when we can instead write DSPACE(f). Should we change all the DSPACE(f) in this article to DSPACE(O(f))? Currently some notations in this article (definitions of REG, L) use big O and others (PSPACE, EXPSPACE) don't which is inconsistent. Similarly for the NSPACE, DTIME articles. Hwzh0 (talk) 13:43, 31 January 2024 (UTC)