Arrays

There are two types of arrays. Static and dynamic ones.

Static means that as we declare our array we need to specify the size of it, to let your operating sytem know how much memory slots/ bytes it should allocate. If it would be 32 bit integer then 4 bytes (slots), if 64 bit integer, then 8 memory slots.

Time complexities of standard arrays operations:

T - Time complexity; S - Space complexity; None - ST complexity

• Accessing a value at a given index: O(1)
• Updating a value at a given index: O(1)
• Iterating over: O(n) T, O(1) S
• Inserting a value at the beginning: O(n)
• Inserting a value in the middle: O(n)
• Inserting a value at the end:
  • amortized O(1) when dealing with a dynamic array
  • O(n) when dealing with a static array
• Removing a value at the beginning: O(n)
• Removing a value in the middle: O(n)
• Removing a value at the end: O(1)
• Copying the array: O(n)

Why updating and getting is constant?

As we know the memory address of first element then we may multiply the number of bytes that is needed for single element, so if its 32-bit integer then it would be 4 bytes. So imagine that array is placed in memory slot under address 8 so as we know that and also how many bytes took single element as its fixed. We can just multiply 4 bytes and for example 3 as we want to get element under index three. So 8 + 4 * 2 = 16. Third element would be under 16 memory slot.

In Java dynamic arrays are respectively vectors and ArrayLists, and in js and python and few other modern languages, standard arrays under the hood are dynamic arrays.

Dynamics arrays means that when we create array with three 64-bit integers, not 24 memory slots will be taken but 48, so it would be generally doubled (may differ on language/ operating system) and that second half will be empty and ‘reserved’ for us which will allows us faster insertions. So when it has space its O(1) but when the last memory slot will be taken, then the next insertions will perform copy of an array and also doubled it in size, and insert new element, then it will be O(n), but as more elements are added the rarely it happened, so we assume that insertions for dynamic arrays AT THE END of array have O(1) complexity, if we want to insert at the beginning or in the middle then it would be O(n), because we need to make a copy of the array shift elements and so on.