2

For example. I have a function which generates an array with random numbers.

int[] generateNum(int n) {
   int[] result = new int[n];
    /* Logic to generate random number */
    ...............
    return result;
}

Then space complexity of the above program should be O(n) or O(1)?

This question is more of about space complexity and very specific about whether to count data structure holding result in space complexity.

Bhushan Jagtap
  • 31
  • 3
  • Only if you have to loop over that whole `result` array to obtain the result. – Robert Harvey Feb 19 '19 at 03:09
  • 1
    Possible duplicate of [What is O(...) and how do I calculate it?](https://softwareengineering.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) – gnat Feb 19 '19 at 04:26
  • 2
    It is O(n) because the size of the array is n. I'm not exactly sure what you mean by output space, but the space requirement would be the same if you didn't return the array. – JacquesB Feb 19 '19 at 07:48
  • @gnat This question is more of about space complexity and very specific about whether to count data structure holding result in space complexity. – Bhushan Jagtap Feb 19 '19 at 14:21
  • @JacquesB Thank you for the reply. Output space = data structure needed to store the result. We do not consider the space allocated to store the input in the analysis. Similarly, do we need to consider the space allocated to store a result in space analysis? – Bhushan Jagtap Feb 19 '19 at 14:24
  • 1
    @BhushanJagtap: Yes, the data structure needed to store the result is included in the space complexity. The space allocated for input should also be included. – JacquesB Feb 19 '19 at 19:48
  • @gnat: enlighten me - I have no idea why someone could think those other question and answer provides anything to answer the current question. So what am I missing? – Doc Brown Feb 27 '19 at 06:41
  • @DocBrown per my reading of the question OP needs to familiarize with basics of this topic which seem to be addressed in duplicate – gnat Feb 27 '19 at 07:59

1 Answers1

3

When a function or algorithm allocates n atomic items of memory like 

   int[] result = new int[n];

then it has a space complexity of at least O(n), regardless of what this array is used for. If it is used exclusively for returning some results, or for a completely different purpose, does not matter.

However, many programming languages allow to return sequences of arbitrary numbers of items in ways the space complexity stays O(1), utilizing streams or generator expressions. For example, in C# you can write

IEnumerable<int> generateNum(int n) 
{
   for(int i=0;i<n;++i)
   {
       r= /* expression to generate random number */;
       yield return r; 
   }
}

Now it is up to the callers what they do with the result - if they process it sequentially, space complexity can stay O(1). If they store the full result in a list or an array, space complexity will be again O(n) at least.

(In Java, this seems to be possible, too, using Iterable<int>, but it seems to require more code).

Doc Brown
  • 199,015
  • 33
  • 367
  • 565