What is the time complexity of declaring and defining, but not initializing, an array in C? For what reason is the answer the case?
I am interested in the time complexity at both compile and run time, but more so run time.
Here is an example of a program with such an array:
int main ()
{
int n[ 10 ]; /* n is an array of 10 integers */
return 0;
}
If it is not O(1), constant time, is there a language that does declare and define arrays in constant time?
The language doesn't specify this. But in typical implementations, space for all local variables in a block is allocated simply by adjusting the stack pointer by the total size of all the variables when entering that block, which is O(1). Arrays are simply included in that total size, and it's calculated at compile time. VLAs are not allocated when the block is entered, the allocation is delayed until the execution of the declaration (since it depends on a variable which must be assigned first), but it's still just an O(1) operation of adjusting the SP register.
I think many implementations actually allocate all the space for a function when entering the function, rather than adjusting the SP for each block. But variables that exist in blocks that do not overlap may share the same memory in the stack frame. But this is not really relevant for the question asked, unless you're wondering if there's a difference between
int a[10];
int b[10];
// code that uses a and b
and
int a[10];
{
int b[10];
// code that uses a and b
}
The compile-time complexity is O(1) for each variable (it just needs to look up the size of the datatype, and multiply by the size if it's an array), so O(n) where n is the number of local variables.
This is a strange and probably unanswerable question. Normally complexity analysis and "big O" notation are applied to algorithms, not so much implementations. But here you're essentially asking entirely about implementation, and of the non-algorithmic, "noise" or "overhead" activities of allocating arrays.
Defining and declaring are compile-time concepts, and I've never heard big-O applied to compile-time activities.
At run time, there may be some work to do to cause the array to spring into existence, whether or not it's initialized. If it's a local ("stack") array, the OS may have to allocate and page in memory for the new function's stack frame, which will probably be more or less O(n) in the array's size. But if the stack is already there, it will be O(0), i.e. free.
If the array is static and/or global, on the other hand, it only has to get allocated once. But, again, the OS will have to allocate memory for it, which might be O(n). The OS might or might not have to page the memory in -- depends on whether you do anything with the array, and on the OS's VM algorithm. (And once you start talking about VM performance, it gets very tricky to define and think about, because the overhead might end up getting shared with other processes in various ways.)
If the array is global or static, and if you don't initialize it, C says it's initialized to 0, which the C run-time library and/or OS does for you one way or another, which will almost certainly be O(n) at some level -- although, again, it may end up being overlapped or shared with other activities in various complicated or unmeasurable ways.
In C, the cost of instantiating a variable at run time (whether a scalar or an array) is (usually) down in the noise, although it really depends on the underlying platform. For example, setting aside space for auto variables on an x86 platform is (usually) done by simply adjusting the stack pointer:
subq $X, %rsp
where X is the amount of storage required for all local variables in the function. So it takes the same amount of time whether X is 4 or 4K1.
Storage for static variables may be allocated from within the program image itself, such that the storage is set aside as soon as the program is loaded into memory (making it effectively zero-cost at runtime).
Or not.
Big O notation doesn't really apply here; the exact mechanisms for allocating storage can vary a lot based on the implementation, and much of it is out of your control. Space is usually the limiting factor here, not time.
