Arrays

Question 1

Basics

Answer 1

• The memory slots reserved are fixed, based on the size of the array
  Arrays types
• Static arrays are those whose size must be declared (Arrays in Java)
• Dynamic arrays (ArrayLists in Java):
  * Are those whose size can be changed
  * Allow having faster insertions by reserving twice memory slots than the specified size
  * Once the allocated space is full, the array is copied into another array of double the size of the previous array

Question 2

Space-time complexities 1

Answer 2

• Accessing an element in an array is an instant / constant operation. It’s O(1) ST
• Setting (overwriting) a value of an element in an array is an instant / constant operation. It’s O(1) ST
• Initializing an array is a linear operation. It’s O(size * N), which is equal to O(N) ST
• Traversing an array is a linear operation. It’s O(size * N), which is equal to O(N) T, O(1) S
• Built-in operations that traverse an array have the same space-time complexities as the traversing operation. It’s O(size * N), which is equal to O(N) T, O(1) S

Question 3

Space-time complexities 2

Answer 3

• Copying an array is a linear operation. It’s O(N) ST
• Inserting a new value in an array consists of a copy operation plus allocating memory for the new value. It’s a varying operation, depending on the position to be added, and the array type:
  * At the beginning: O(N) T, O(1) S
  * In the middle: O(N) T, O(1) S
  * At the end: amortized O(1) T on dynamic arrays, O(N) T on static arrays; O(1) S
• Removing a value in an array depends on the position to be removed. Many cases consist of a shifting operation:
  * At the beginning: O(N) ST
  * In the middle: O(N) ST
  * At the end: O(1) ST