Arrays

About Arrays

• Arrays are built into most programming languages.
• We use arrays to store items sequentially.

Advantages of arrays

• Arrays are the optimal data structures when we are trying to access the data via the index
• because the retrieval of the element from the array via the index is O(1)

Dis-advantages of arrays

• Arrays are static meaning when creating the arrays we need to mention the size, As a result, we need to know ahead of time how many items we need to store in an array.
• Possibility may arise that we end up allocating more space than needed and end up losing the space.
• Another possibility is that we may also end up needing more space and as a result requiring to resize the array into a new array and copy all the elements from the old array to the new array.

Time Complexity of operations

• Operation performed on arrays are insertion, deletion, lookup
  • Insertion ----> Run time complexity is be O(n) - This is because the cost of copying the items from the old array to the new array is O(n) since complexity increases with the size of the input. This is the worst possible scenario when the array is full and we might need to resize them to accommodate more items.
  • lookup -------> Run time complexity is O(1) - This is because accessing via the index is fastest in the case of the array.
  • Deletion -----> Run time complexity is O(n) - In the beast, the case is said item to be deleted is at the end of the array. It's easy to access the item from the end but when calculating the time complexity we need to consider the worst-case scenario due to this there is the possibility item is at the beginning of the array, in this scenario we not only have to delete the element but we also need to shift all the elements next to it one place to left and this increases linearly on the size of the input.