[deltaknight]

I’m not sure this definition of Big-O for space complexity is universal. When I’ve seen/used it, the size of the initial data wasn’t relevant, it was more about the additional memory required for the algorithm.

For example, an in-place algorithm like Bubble Sort would have a O(1) space complexity, because it requires no extra memory (and 0 memory is a constant). Merge sort on the other hand is O(n) because it always uses additional memory for its intermediate stages, and that additional memory scales with n.

Doing a quick google, the first few sites I find seem to use a similar understanding https://www.geeksforgeeks.org/time-and-space-complexity-anal...

[aleksiy123]

The confusion is around space complexity vs auxiliary space complexity (extra space).

space complexity is O(n) but auxiliary space complexity uses Theta for notation instead.

But people aren't too picky on the notation and usually say something like "O(1) extra space" instead of using theta.

https://en.m.wikipedia.org/wiki/Space_complexity

[nneonneo]

That’s not quite accurate. Big O notation and Theta notation are different ways of expressing the growth rates of functions - the choice of using Big O or Theta is independent of whether you’re trying to specify total space complexity or auxiliary space complexity.

Saying something is O(n) tells you it grows at most linearly, but this would also admit e.g. log n.

Saying something is Theta(n) tells you it grows exactly linearly: that is, it is not a slower growth rate like log n, nor a faster growth rate like n^2.

[aleksiy123]

Yeah, you are correct I misinterpreted the article.

But yeah I guess space complexity vs auxiliary space complexity is just a bit ambigous.