1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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.
|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why would the length of encoding be considered Θ(log n) and not Θ(1)? Is it because at this conceptual level we are supposed to think that an integer can be arbitrarily large and thus require an arbitrary number of bits as opposed to be capped at 32 or 64 bits? $\endgroup$ – lolski Nov 18 '19 at 8:57
  • 1
    $\begingroup$ Encoding an integer between $0$ and $2^x-1$ requires $O(x)$ bits but often times the time or space complexities of algorithms don't have a strong dependence on the value of the integers involved. In this case integers are often assumed to use $O(1)$ space, or "fit into a memory word". Think, e.g., of the sorting problem where the focus is on the number of elements rather than their values. For a more precise description than what fits in a comment see Word Ram and Cost models. $\endgroup$ – Steven Nov 18 '19 at 9:19
  • 1
    $\begingroup$ To be pedantic: weird things happen if you assume that arbitrary large integers can fit into $O(1)$ bits/words. For example you cold compress any binary string into a single integer by just taking the integer whose binary representation matches the string. Also, if you assume that the input $n$ to your function is a $32$ or $64$ bit integer, then the complexity would be $O(n)=O(1)$ since $n$ is upper bounded by a constant, namely $2^{64}$. Since you are (probably) interested in the asymptotic behavior of your algorithm, it makes sense to consider $n$ as an arbitrarily large integer. $\endgroup$ – Steven Nov 18 '19 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.