In calculating space complexity, we don’t consider the input size. we only consider the extra space allocated. so my question is Do we consider output space while calculating space complexity?
For example, let’s consider the function that return some value. so in function body, I have dedicated variable like output or res, that I am going to use for returning from function.
Will the space of output or res variable count while calculating space complexity?
Thank you.
I think the answer is “maybe” because it likely depends on the question. For example, if I ask you to reverse a list in place then the space of the result is already accounted for by the input so I am really only asking what more do you need. However, if you need to return “a data structure” that has some property, then the amount of space the result takes up matters. Having a solution that includes storing some duplicate data may have trade-offs that could be important.
For the most part, your intuition seems right, but usually the temporary structures you need to create to solve the problem will already account for the exact size of the output already so it is basically accounted for anyway. For example, if I need to get the three smallest integers in an unbalanced binary tree, I am certainly going to need to keep track of at least 3 integers. Make sense?