What is the complexity of using arrays and hash tables?

Arrays

• Fixed size: Resizing an array (adding/removing elements) can be resource-intensive, requiring allocation of new memory and copying data.
• Inefficient insertion/deletion in the middle: Inserting or deleting an element in the middle of an array requires shifting all subsequent elements, which takes time proportional to the number of shifted elements (O(n)).
• Type safety (in some languages): In strictly typed languages, arrays can only store elements of a single data type, limiting flexibility.

Hash tables (dictionaries)

• Collisions: The possibility of hash collisions (different keys producing the same hash), which requires additional mechanisms for resolution (open addressing, chaining) and increases access time.
• Unordered: Elements in a hash table do not have a guaranteed order, which can be inconvenient when iteration in a specific sequence is needed.
• Need for hashable keys: Keys must be immutable (hashable) and have a properly implemented hash function. Mutable objects (e.g., lists) cannot be keys.
• Memory costs: Hash tables may consume more memory than arrays due to the need to store additional information (e.g., pointers to chains).

# Example of inserting in the middle of a list (analogous to array modification in Python)
my_list = [1, 2, 4, 5]
my_list.insert(2, 3) # Shifts elements

# Example of creating an immutable key for a dictionary
my_dict = {tuple([1, 2]): "value"}