The space complexity of a function that allocates space based on the input value and not size

Question

What is the space complexity of the following hyphotetical function:

void function(int n) {
  int[] array = new int[n]; // allocate array of size n
  return;
}

My intuition tells me that it is not O(n). Because the function will allocate an array of size n where n is the value of the input and not the size. The input size is constant because it is a single integer.

Answer 1

It is $O(n)$ and, more precisely, $\Theta(n)$. What might be confusing you is the fact that the length of the encoding of the parameter $n$ will only be $\Theta(\log n)$, meaning that the value of $n$ (and hence the space required by the function) is exponentially larger than the size of the input to function (i.e., the number of bits needed to represent $n$).

To summarize both the following statements are true:

• function(n) requires linear space w.r.t. the value of its parameter $n$, i.e., the asymptotic space complexity of function(n) is $O(n)$;
• function(n) requires an exponential amount of space w.r.t. the length of the encoding of its input.