CODEWITHSUNDEEP
data-structuresbig-obinary-search-treespace-complexity
coder
coder

Reputation: 11

space complexity of iterative binary search

I'm trying to understand the space complexity of iterative binary search. Given the space complexity is input size + auxiliary space, shouldn't the space complexity depend on the input size? why is it always O(1)?
If we compare the space complexity between tree A(the height of the tree is 1) and tree B(the height of the tree is 1,000) I think the space complexity should be different. Could someone please explain me why it should be the same regardless of the input size?

Upvotes: 0

Views: 221

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59293

Given the space complexity is input size + auxiliary space...

Yes, but this premise is incorrect. I checked the Web and there seem to be a lot of sites that define space complexity this way, and then go on to mention sublinear space complexities as if there were no contradiction. It's no wonder that people are confused.

This definition is really just wrong, because it is always correct to interpret a space complexity as referring to auxiliary space only.

If a stated space complexity is sublinear, then it obviously cannot include the input space, so you should interpret it as referring to auxiliary space only.

If a stated space complexity is not sublinear, then it is correct whether it includes the input space or not, and in fact it means exactly the same thing in both cases, so you can't go wrong by assuming that it refers to auxiliary space only.

Including the input space in your definition of space complexity can only reduce the set of complexity statements that your definition applies to, and the meaning when it does apply is unchanged, so that makes it strictly less correct as a definition.

Upvotes: 1

Related Questions