VietMX Staff asked 3 years ago
Array uses continuous memory locations (space complexity O(n)) to store the element so retrieving of any element will take O(1) time complexity (constant time by using index of the retrieved element). O(1) describes inserting at the end of the array. However, if you’re inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n) for arrays. End appending also discounts the case where you’d have to resize an array if it’s full.
| Operation | Average Case | Worst Case |
|---|---|---|
| Read | O(1) |
O(1) |
| Append | O(1) |
O(1) |
| Insert | O(n) |
O(n) |
| Delete | O(n) |
O(n) |
| Search | O(n) |
O(n) |
