This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

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)Reply

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)Reply

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)Reply

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)Reply