In Big O notation, allocate an array of N element is defined by O(1) or O(n) ? For example in C#, if I allocate an array like this :
int[] a = new int[10]
When I display this array, I have :
{0,0,0,0,0,0,0,0,0,0}
1 Answer
Normally, size of an array has no effect on complexity of allocation itself. AFAIK, an array is internally a pointer to some address where the array begins and hidden fields for element size and element count. So it would be O(1).
At least this is the case in Object Pascal, though I am not sure for C# or other languages.
But finding the chunk of memory which fits for your array has some higher complexity which depends on the size at some point but is more dependent to how the active memory manager works: Time complexity of memory allocation.
-
2Note that
new[](in C# and also in C++) not only allocated but also initializes.– user7043Nov 12, 2014 at 10:27 -
-
If the system keeps an arena of pre-initialized memory around, then allocating would normally amount to incrementing a pointer, so the amortized cost would still be constant, not linear. Nov 12, 2014 at 10:32
-
@KilianFoth Yes, it's certainly possible to get initialization at no extra cost during allocation (though it probably makes other operation, e.g. deallocation, more expensive). But in any case it is a facet that must be considered.– user7043Nov 12, 2014 at 10:35
new[]is considered a primitive operation in your model of computation, or on the assumed implementation ofnew[]if it's not. Adding two integers may take O(1) time in the RAM model, or O(d) on a Turing machine (where d = the length of the numbers).